Results 1 to 3 of 3

Math Help - Infinity of primes through fermat numbers

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    36

    Infinity of primes through fermat numbers

    I have proved that if (2^m) + 1 is prime, then m = 2^n for some n.
    Also , I have managed to show that for the nth Fermat number, F_n =
    (2^2^n) + 1, if a =/= b, the gcd(F_a, F_b) = 1.
    Finally I have shown that if p is prime and p divides F_n, then 2^
    (n+1) divides (p-1).

    My question is:

    How do you deduce that for each n, there are infinitely many primes
    congruent to 1(mod 2^n)?


    This is how I have approached it so far but am not sure.


    Suppose for a contradiction that there are only finitely many primes
    congruent to 1 modulo 2^n.
    Label them p_1, ..., p_n.
    .
    Consider x = 2*p_1...p_n
    and N = x^(2^(n-1))+ 1

    Because x is divisible by 2, x^2 is congruent to 0 (mod 2^n).
    So N is congruent to 1 (mod 2^n).
    Also, we note that N is congruent to 1(mod p_i) for each of the p_i.

    Assume N is not prime.
    Then there exists a prime q such that q divides N = x^(2^(n-1))+ 1.
    So x^(2n-1) is congruent to -1(mod q).
    => x^(2n) is congruent to 1(mod q).
    => 2^n divides (q-1) by PART iii
    => q is congruent to 1(mod 2^n)

    Thus q is one of the p_i for some i.

    CONTRADICTION
    (since N is congruent to both 0(mod q) and 1(mod p_i))
    => N is prime

    But since N > p_i, and N is congruent to 1 (mod 2^n), this is again
    a CONTRADICTION.

    Since either assuming N is prime or assuming N is composite leads to
    a contradiction, there must be infinitely many primes congruent to 1
    (mod 2^n).


    Thanks for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Your proof is almost perfect.

    The contradiction comes from assuming  p_1, p_2, \cdot\cdot\cdot, p_n were all the primes of the form  2^n+1 , then finding the prime  q = 2^k+1 and observing  q > p_i \; \forall i .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    Ah ok so have I used part (iii) correctly?
    Glad to know it is mostly correct as I was previously told that it was not though I doubted it so I thought I would post it back on here!

    Thanks very much
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof that all numbers are products of primes?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 8th 2011, 01:56 AM
  2. Questions about Fermat numbers?
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 25th 2010, 02:24 PM
  3. Fermat Numbers Problems
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: May 14th 2010, 11:34 AM
  4. Factoring numbers into product of primes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2010, 05:17 AM
  5. Writing numbers as sum of primes
    Posted in the Number Theory Forum
    Replies: 16
    Last Post: December 21st 2009, 12:16 PM

Search Tags


/mathhelpforum @mathhelpforum