Scribd Logo
Upload

Welcome to Scribd!

  • 46 views

    New Zealand Mathematical Olympiad Committee Primes That Are Sums of Two Squares

    Uploaded by

    n
    This document summarizes several number theory concepts including congruences, Fermat's theorem on primes of the form 4n + 1, and Wilson's theorem. It proves Fermat's theorem using the pigeonhole principle and Wilson's theorem. Specifically: 1) It defines congruences and states properties like if a ≡ b (mod m) and c ≡ d (mod m) then a + c ≡ b + d (mod m). 2) It proves Wilson's theorem that (p-1)! ≡ -1 (mod p) for any prime p. 3) It uses the pigeonhole principle to prove Fermat's theorem that any prime of the form

    Copyright:

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

    New Zealand Mathematical Olympiad Committee Primes That Are Sums of Two Squares

    Uploaded by

    n
    46 views3 pages
    This document summarizes several number theory concepts including congruences, Fermat's theorem on primes of the form 4n + 1, and Wilson's theorem. It proves Fermat's theorem using the pigeonhole principle and Wilson's theorem. Specifically: 1) It defines congruences and states properties like if a ≡ b (mod m) and c ≡ d (mod m) then a + c ≡ b + d (mod m). 2) It proves Wilson's theorem that (p-1)! ≡ -1 (mod p) for any prime p. 3) It uses the pigeonhole principle to prove Fermat's theorem that any prime of the form

    Original Description:

    fermat

    Original Title

    Fermat 1

    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 summarizes several number theory concepts including congruences, Fermat's theorem on primes of the form 4n + 1, and Wilson's theorem. It proves Fermat's theorem using the pigeonhole principle and Wilson's theorem. Specifically: 1) It defines congruences and states properties like if a ≡ b (mod m) and c ≡ d (mod m) then a + c ≡ b + d (mod m). 2) It proves Wilson's theorem that (p-1)! ≡ -1 (mod p) for any prime p. 3) It uses the pigeonhole principle to prove Fermat's theorem that any prime of the form

    Copyright:

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

    New Zealand Mathematical Olympiad Committee Primes That Are Sums of Two Squares

    Uploaded by

    n
    This document summarizes several number theory concepts including congruences, Fermat's theorem on primes of the form 4n + 1, and Wilson's theorem. It proves Fermat's theorem using the pigeonhole principle and Wilson's theorem. Specifically: 1) It defines congruences and states properties like if a ≡ b (mod m) and c ≡ d (mod m) then a + c ≡ b + d (mod m). 2) It proves Wilson's theorem that (p-1)! ≡ -1 (mod p) for any prime p. 3) It uses the pigeonhole principle to prove Fermat's theorem that any prime of the form

    Copyright:

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

    New Zealand Mathematical Olympiad Committee

    Primes that are Sums of Two Squares


    Arkadii Slinko

    Introduction

    These notes give a number of number theoretic applications of the Pigeonhole Principle. In particular we prove
    Fermats theorem on primes of the form 4n + 1.

    Congruences

    First a short summary of some facts about congruences. An excellent reference for this sections results is
    Richard Courant and Herbert Robbins What is Mathematics? (Section 2, Supplement to Chapter 1).
    Let m be an integer. We write
    a b (mod m),
    and say that a is congruent to b modulo m, if a and b have the same remainder on division by m. Equivalently,
    a b mod m if and only if a b is divisible by m. The following facts about congruences will be used without
    explicit mention, and can be easily proved:
    1. If a b mod m and c d mod m, then a + c b + d mod m.
    2. If a b mod m and c d mod m, then ac bd mod m.
    Lemma 1. Let p be a prime. Then for every positive integer a such that 0 < a < p there exists a unique
    positive integer b such that ab 1 mod p and 0 < b < p.
    The number b will be called the inverse of a modulo p.
    Proof. Let us consider the numbers
    1 a, 2 a, . . . , (p 1) a
    or rather their remainders on division by p. These remainders must be all different. For if
    iaja

    (mod p)

    for some integers 1 i < j p 1 and j, then i a j a = (i j)a must be divisible by p, which is impossible
    as i j and a are both smaller than p.
    Therefore (Pigeonhole Principle!) one of these remainders must be 1. Thus k a 1 mod p for some integer k
    such that 0 < k < p 1, and we can set b = k. Suppose that this inverse is not unique; that is, that there is
    another positive integer c such that 0 < c < p and ac 1 mod p. Then we can consider the product bac, for
    which we will have
    bac = (ba)c 1 c = c (mod p),
    bac = b(ac) b 1 = b (mod p).
    Hence b c mod p, which implies b = c.
    Theorem 2 (Wilson). Let p be a prime. Then
    (p 1)! 1 mod p.
    1

    Proof. Modulo p, the residues 1 and p 1 are their own inverses. We claim there are no other such residues.
    Indeed, if x2 1 mod p, for some 0 < x < p, then x2 1 0 mod p. That is, x2 1 = (x 1)(x + 1) is divisible
    by p, which means either x 1 or x + 1 is divisible by p. Thus x = 1 or x = p 1.
    This means that all numbers 2, 3, . . . , p 2 can be split into pairs so that in each pair the integers are mutual
    inverses. Hence
    (p 2)! 1 (mod p).
    So
    (p 1)! = (p 2)!(p 1) p 1 1

    (mod p).

    and Wilsons theorem follows.

    Fermats theorem

    Lemma 3. Let n > 1 be


    a positive integer.Then for every positive integer u there exist integers x, y,not both
    zero, such that 0 |x| n and 0 |y| n and xu y mod n.

    Proof. Let k = b nc be the integer part of n. Then k 2 n < (k + 1)2 . Let us consider the (k + 1)2 integers
    xu y,
    where both x and y take values from the set {0, 1, 2, . . . , k}. As n < (k + 1)2 , we have more such differences than
    remainders on dividing by n. Thus, by the Pigeonhole Principle, two such differences are congruent modulo n;
    that is,
    x1 u y1 x2 u y2 (mod n)
    for some x1 , x2 , y1 , y2 , where either x1 6= x2 or y1 6= y2 . Hence
    (x1 x2 )u y1 y2 ,
    and x = x1 x2 and y = y1 y2 satisfy the conditions of the lemma.
    Theorem 4 (Fermat). Let p = 4n + 1 be a prime. Then there exist positive integers x and y such that
    x2 + y 2 = p.
    Proof. We will prove, first, that u2 1 mod p for u = ((p 1)/2)!. We note that
    p1

    (mod p),

    p2

    (mod p),

    ...
    (p 1)/2 + 1

    (p 1)/2

    (mod p)

    where we have (p 1)/2 = 2n, i.e. an even number, of such pairs. Multiplying them all, we get
    (p 1)!
    (1)2n (((p 1)/2)!) = (((p 1)/2)!)
    ((p 1)/2)!

    (mod p).

    Since, by Wilsons theorem


    (p 1)! 1

    (mod p),

    this implies
    1 (p 1)! (((p 1)/2)!)2 = u2
    Now we will use Lemma 3, to find two integers x, y such that
    1. 0 |x|

    p and 0 |y|

    p; and,
    2

    (mod p).

    2. xu y mod p.

    Since p is not a whole number, the inequalities in the first property are strict; that is, 0 |x| < p and

    2
    2
    0 |y| < p. So x < p and y < p, and hence
    0 < x2 + y 2 < 2p.
    From the second property, we get that y 2 x2 u2 x2 mod p, so
    x2 + y 2 0 mod p
    Combining these gives x2 + y 2 = p, which proves the theorem.

    Problems
    1. Given n pairwise coprime positive integers which are greater than 1 but smaller than (2n 1)2 , prove that
    at least one of them is prime.
    January 24, 2009
    http://www.mathsolympiad.org.nz

    You might also like