Scribd Logo
Upload

Welcome to Scribd!

  • 93 views

    Number Theory

    Uploaded by

    Joshua John Julio
    This document discusses several number theory methods for determining the remainders when large numbers are divided: 1. Fermat's Little Theorem and Euler's Totient Function can be used to find the remainders of exponential expressions like 2201 mod 7 or the last two digits of 20172042. 2. The Chinese Remainder Theorem can find a number that satisfies simultaneous congruences, like the smallest four-digit number where the last four digits of its square are itself. 3. Wilson's Theorem gives (p-1)! congruent to -1 mod p for any prime p, allowing us to determine the remainder of 2014! divided by 2017.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Number Theory

    Uploaded by

    Joshua John Julio
    93 views2 pages
    This document discusses several number theory methods for determining the remainders when large numbers are divided: 1. Fermat's Little Theorem and Euler's Totient Function can be used to find the remainders of exponential expressions like 2201 mod 7 or the last two digits of 20172042. 2. The Chinese Remainder Theorem can find a number that satisfies simultaneous congruences, like the smallest four-digit number where the last four digits of its square are itself. 3. Wilson's Theorem gives (p-1)! congruent to -1 mod p for any prime p, allowing us to determine the remainder of 2014! divided by 2017.

    Original Description:

    theory of no.

    Original Title

    Number-Theory

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses several number theory methods for determining the remainders when large numbers are divided: 1. Fermat's Little Theorem and Euler's Totient Function can be used to find the remainders of exponential expressions like 2201 mod 7 or the last two digits of 20172042. 2. The Chinese Remainder Theorem can find a number that satisfies simultaneous congruences, like the smallest four-digit number where the last four digits of its square are itself. 3. Wilson's Theorem gives (p-1)! congruent to -1 mod p for any prime p, allowing us to determine the remainder of 2014! divided by 2017.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    93 views2 pages

    Number Theory

    Uploaded by

    Joshua John Julio
    This document discusses several number theory methods for determining the remainders when large numbers are divided: 1. Fermat's Little Theorem and Euler's Totient Function can be used to find the remainders of exponential expressions like 2201 mod 7 or the last two digits of 20172042. 2. The Chinese Remainder Theorem can find a number that satisfies simultaneous congruences, like the smallest four-digit number where the last four digits of its square are itself. 3. Wilson's Theorem gives (p-1)! congruent to -1 mod p for any prime p, allowing us to determine the remainder of 2014! divided by 2017.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    METHODS IN DETERMINING REMAINDERS OF LARGE DIVIDENDS

    1. Fermat’s Little Theorem

    ap−1 ≡ 1 (mod p)
    Where p is a prime number and a is any positive integer.

    * Determine the remainder when 2201 is divided by 7

    By Fermat’s Little Theorem, 26 ≡ 1(mod7). Thus,

    2201 = (26 )33 ∗ 23


    ≡ 133 ∗ 23 (mod7)
    = 8 (mod7)
    201
    2 ≡ 1 (mod7)

    2. Euler’s Totient Function

    aφ(n) ≡ 1 (modn)
        
    1 1 1
    If and only if gcd(a, n) = 1. Also, φ(n) = n 1 − 1− ··· 1 − where n = pa11 pa22 · · · pakk
    p1 p2 pk

    * Determine the last 2 digits of 20172042


      
    1 1
    We have φ(100) = 100 1 − 1− = 40
    2 5
    So 201740 ≡ 1 (mod100)

    20172042 = (1740 )501 ∗ 172


    ≡ 1501 ∗ 289 (mod100)
    ≡ 89 (mod100)

    3. Chinese Remainder Theorem A number n that satisfies

    x ≡ a1 (modr1 )
    ≡ a2 (modr2 )
    ≡ a3 (modr3 )
    ···
    ≡ ak (modrk )

    Can be expressed as a single module x ≡ b(mod lcm(r1 , r2 , · · · , rk ))

    * Determine the smalllest four digit integer n such that the last 4 digits of n2 is n.

    We have n2 ≡ n(mod10000). Meaning, n(n − 1) ≡ 0(mod104 ).


    Since 104 = 24 · 54 , we have 2 possible cases.
    (a) n ≡ 0(mod24 ), n − 1 ≡ 0(mod54 )
    We have two modulos for a single variable, which are: n ≡ 0(mod16) ≡ 1(mod625)
    Since n ≡ 0(mod16), We deduce that n = 16a. But n ≡ 1(mod625)

    n ≡ 1(mod625)
    16a ≡ 1
    16a ≡ −624
    a ≡ −39
    a ≡ 586(mod625)
    a = 625b + 586

    Thus, the value of n for the first case is n = 16(625b + 586) = 10000b + 9376. The smallest value
    of n in that case is 9376.
    (b) n ≡ 0(mod625), n − 1 ≡ 0(mod16)
    So we have n ≡ 0(mod625) ≡ 1(mod16)

    n ≡ 1(mod16)
    625a ≡ 1
    a ≡ 1(mod16)
    a = 16b + 1

    Thus, we have n = 625(16b + 1) = 10000b + 625 The smallest value of n in this case is 625.
    Finally, the smallest value of a four-digit n is 9376 .

    4. Wilson’s Theorem
    For a prime p,

    (p − 2)! ≡ 1(modp)

    *Determine the remainder when 2014! is divided by 2017. Since 2017 is a prime, by Wilson’s theorem,

    2015! ≡ 1(mod2017)

    2015! ≡ 1(mod2017)
    2015 ∗ 2014! ≡ 1(mod2017)
    −2 ∗ 2014! ≡ −2016(mod2017)
    2014! ≡ 1008 (mod2017)

    You might also like