Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help with a proof.

  1. Jan 22, 2004 #1
    Let [tex]n \geq 2[/tex] be an integer such that [tex]2^n + n^2[/tex] is prime. Prove that [tex]n \equiv 3(mod 6)[/tex].

    Ok this is what i have so far.
    [tex]n \equiv 3(mod 6)\\ \Rightarrow 6|n-3\\ \Rightarrow n - 3 = 6k \\ \Rightarrow n = 6k + 3 \\[/tex].

    Ok well i think i can use a proof by contradition. Obviosly [tex]n[/tex] cannot be an even number because [tex]2^n + n^2[/tex] wont be prime. So [tex]n[/tex] must be [tex]6k + 1[/tex] or [tex]6k + 3[/tex] or [tex]6k + 5[/tex]. Now when i plug all these into [tex]2^n + n^2[/tex] and mess around with it for a bit i just can't seem to prove it. Can anyone help me out?
  2. jcsd
  3. Jan 23, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It suffices to consider the 2^n + n^2 mod 3.

    Clearly, if n is NOT congruent to 0 mod three, then as n must be odd, 2^n = -1 mod 3 and n^2 = 1 mod 3, thus 2^n + n^2 =0 mod 3 and can't be prime (n=1 excepted)

    Hence n is divisble by 3, and not by two, thus it is congruent to 3 mod 6
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook