Scribd Logo
Upload

Welcome to Scribd!

  • 369 views

    Wilson Fermat Ejercicio

    Uploaded by

    Juancho Parra
    The document discusses Wilson's theorem and Fermat's theorem, which relate to primality testing and solving congruences. It proves Wilson's theorem, which states that p is prime if and only if (p-1)! = -1 (mod p). It also proves Fermat's theorem, which states that if p is prime and p does not divide a, then ap-1 = 1 (mod p). Examples are provided to demonstrate solving congruences using these theorems.

    Copyright:

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

    Wilson Fermat Ejercicio

    Uploaded by

    Juancho Parra
    369 views3 pages
    The document discusses Wilson's theorem and Fermat's theorem, which relate to primality testing and solving congruences. It proves Wilson's theorem, which states that p is prime if and only if (p-1)! = -1 (mod p). It also proves Fermat's theorem, which states that if p is prime and p does not divide a, then ap-1 = 1 (mod p). Examples are provided to demonstrate solving congruences using these theorems.

    Original Description:

    Wilson’s Theorem and Fermat’s Theorem y ejercicios de como obtener modulos de cierto numero par

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses Wilson's theorem and Fermat's theorem, which relate to primality testing and solving congruences. It proves Wilson's theorem, which states that p is prime if and only if (p-1)! = -1 (mod p). It also proves Fermat's theorem, which states that if p is prime and p does not divide a, then ap-1 = 1 (mod p). Examples are provided to demonstrate solving congruences using these theorems.

    Copyright:

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

    Wilson Fermat Ejercicio

    Uploaded by

    Juancho Parra
    The document discusses Wilson's theorem and Fermat's theorem, which relate to primality testing and solving congruences. It proves Wilson's theorem, which states that p is prime if and only if (p-1)! = -1 (mod p). It also proves Fermat's theorem, which states that if p is prime and p does not divide a, then ap-1 = 1 (mod p). Examples are provided to demonstrate solving congruences using these theorems.

    Copyright:

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

    6-22-2008

    Wilsons Theorem and Fermats Theorem


    Wilsons theorem says that p is prime if and only if (p 1)! = 1 (mod p).
    Fermats theorem says that if p is prime and p 6 | a, then ap1 = 1 (mod p).
    Wilsons theorem and Fermats theorem can be used to reduce large numbers with respect to a give
    modulus and to solve congruences. They are also used to prove other results in number theory for
    example, those used in cryptographic applications.

    Lemma. Let p be a prime and let 0 < k < p. k2 = 1 (mod p) if and only if k = 1 or k = p 1.
    Proof. If k = 1, then k2 = 1 (mod p). If k = p 1, then
    k2 = p2 2p + 1 = 1 (mod p) .
    Conversely, suppose k2 = 1 (mod p). Then
    p | k2 1 = (k 1)(k + 1),
    and since p is prime, p | k 1 or p | k + 1. The only number in {1, . . . , p 1} which satisfies p | k 1 is 1,
    and the only number in {1, . . . , p 1} which satisfies p | k + 1 is p 1.
    Theorem. (Wilsons theorem) Let p > 1. p is prime if and only if
    (p 1)! = 1 (mod p) .
    Proof. Suppose p is prime. If k {1, . . . , p 1}, then k is relatively prime to p. So there are integers a and
    b such that
    ak + bp = 1, or ak = 1 (mod p) .
    Reducing a mod p, I may assume a {1, . . . , p 1}.
    Thus, every element of {1, . . . , p 1} has a reciprocal mod p in this set. The preceding lemma shows
    that only 1 and p 1 are their own reciprocals. Thus, the elements 2, . . . , p 2 must pair up into pairs
    {x, x1 }. It follows that their product is 1. Hence,
    (p 1)! = 1 2 (p 2) (p 1) = 1 1 (p 1) = p 1 = 1 (mod p) .
    Now suppose (p 1)! = 1 (mod p). I want to show p is prime. Begin by rewriting the equation as
    (p 1)! + 1 = kp.
    Suppose p = ab. I may take 1 a, b p. If a = p, the factorization is trivial, so suppose a < p. Then
    a | (p 1)! (since its one of {1, . . . , p 1}) and a | p, so (p 1)! + 1 = kp shows a | 1. Therefore, a = 1.
    This proves that the only factorization of p is the trivial one, so p is prime.

    Example. Wilsons theorem implies that the product of any ten consecutive numbers, none divisible by 11,
    equals 1 mod 11 (since any ten consecutive numbers reduce mod 11 to {1, 2, . . . , 10}. For example,
    12 13 20 21 = 1 (mod 11) .

    Example. Find the least nonnegative residue of 70! (mod 5183).


    Note that 5183 = 71 73. Ill start by finding the residues of 70! mod 71 and 73.
    By Wilsons theorem,
    70! = 1 (mod 71) .
    Next, let k = 70! (mod 73). Then
    71 72 k = 70! 71 72 (mod 73) ,
    (2)(1)k = 72! (mod 73) ,
    2k = 1 (mod 73) .
    Note that 2 37 = 74 = 1 (mod 73). So
    37 2k = 37 (1) (mod 73) ,
    k = 37 = 36 (mod 73) .
    Thus,
    70! = 1 (mod 71)

    and

    70! = 36 (mod 73) .

    Ill the the iterative method of the Chinese Remainder Theorem to get a congruence mod 5183. First,
    70! = 1 (mod 71) means 70! = 1 + 71a for some a Z. Plugging this into the second congruence yields
    1 + 71a = 36 (mod 73) ,
    71a = 37 (mod 73) ,
    2a = 37 (mod 73) ,
    (37)(2a) = (37)(37) (mod 73) ,
    a = 1369 = 18 (mod 73) .
    The last congruence means that a = 18 + 73b for some b Z. Plugging this into 70! = 1 + 71a gives
    70! = 1 + 71(18 + 73b) = 1277 + 5183b,

    or 70! = 1277 (mod 5183) .

    Theorem. (Fermat) Let p be prime, and suppose p 6 | a. Then ap1 = 1 (mod p).
    Proof. The idea is to show that the integers
    a, 2a, . . . , (p 1)a
    reduce mod p to the standard system of residues {1, . . . , p 1}, then apply Wilsons theorem.
    There are p 1 numbers in the set {a, 2a, . . . , (p 1)a}. So all I need to do is show that theyre distinct
    mod p. Suppose that 1 j, k p 1, and
    aj = ak (mod p) .
    This means p | aj ak = a(j k), so p | a or p | j k. Since the first case is ruled out by assumption,
    p | j k. But since 1 j, k p 1, this is only possible if j = k.
    Thus, {a, 2a, . . . , (p 1)a} are p 1 distinct numbers mod p. So if I reduce mod p, I must get the
    numbers in {1, . . . , p 1}. Hence,
    a 2a (p 1)a = 1 2 (p 1) = (p 1)! = 1 (mod p) .
    2

    On the other hand, another application of Wilsons theorem shows that


    a 2a (p 1)a = ap1 (p 1)! = ap1 (mod p) .
    So ap1 = 1 (mod p), or ap1 = 1 (mod p).
    Corollary. If p is prime, then ap = a (mod p) for all a.
    Proof. If p | a, then ap = 0 (mod p) and a = 0 (mod p), so ap = a (mod p).
    If p 6 | a, then ap1 = 1 (mod p). Multiplying by a, I get ap = a (mod p) again.

    Example. Compute 50250 (mod 83).


    One way is to multiply out 50250 ; Mathematica tells me it is
    52714787526044456024726519219225572551424023323922008641517022
    09078987540239533171017648022222644649987502681255357847020768
    63325972445883937922417317167855799198150634765625000000000000
    00000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000
    0000000000000000000000000000000000000000000000000000
    Now just reduce mod 83. Heh.
    If you dont have Mathematica, maybe you should use Fermats theorem. 83 6 | 50, so Fermat says
    5082 = 1 (mod 83). Now 3 82 = 246, so
    50250 = 50246 504 = (5082 )3 25002 = 13 102 = 100 = 17 (mod 83) .
    In other words, if youre trying to reduce ak mod p, where p 6 | a, factor out as many ap1 s as possible,
    then reduce the rest by hand.

    Example. Solve 16x = 25 (mod 41).


    Id like to multiply both sides by the reciprocal of 16 mod 41. What is it? Well, I could use the Euclidean
    algorithm on (16, 41), or I could do a multiplication table mod 41. A simpler approach is to note that by
    Fermat, 1640 = 1 (mod 41). Hence,
    1639 16x = 1639 25 (mod 41)

    gives x = 1639 25 (mod 41) .

    Now this is an answer, but a rather cheesy one. I ought to reduce the right side mod 41 to something
    a little smaller! I cant use Fermat any more, so I just divide and conquer.
    162 = 256 = 10 (mod 41), so
    1639 25 = (162 )19 (16 25) = 1019 400 = 1019 31 (mod 41) .
    Now 102 = 100 = 18 (mod 41), so
    1019 31 = (102 )9 (10 31) = 189 310 = 189 23 (mod 41) .
    182 = 324 = 37 (mod 41), so
    189 23 = (182 )4 (18 23) = 374 414 = 1874161 414 = 10 4 = 40 (mod 41) .
    (I reduce down to the point where the arithmetic can be handled by whatever computational tools I
    have available.)

    c 2008 by Bruce Ikenaga


    You might also like