As the title indicates, I do not know how to proceed. There is a hint to prove it. The hint says that:

show that if $p>2$ then a is of order $2^{n+1} \pmod p$.

But I do not see any connection between the hint and the question in demand.

Please help!

Thanks in advance,,


The original question in the title was to prove:

If $p|(a^{2n}+1)$, then $p = 2$ or $p \equiv 1 \pmod {2^{n+1}}$.

By the useful comment of @Zvi below, the statement appears to be false. The statement is originally from "An Introduction to The Theory of Numbers" by Ivan Niven, Herbert S.Zuckerman and Hugh L.Montgomery. Most probably, it is a typo, since the correct statement is:

If $p|(a^{2^{n}}+1)$, then $p = 2$ or $p \equiv 1 \pmod {2^{n+1}}$.

Please consider the latter statement. A useful clue or hint is very helpful.

  • 2
    $\begingroup$ Do you mean $p\mid a^{2^n}+1$, because the statement is false as it is? (Take $a=3$, $p=5$, and $n=3$ so $2^{n+1}=16$. Then, $a^{2n}+1=730$ is divisible by $p$ but $p\not\equiv 1\pmod{16}$.) $\endgroup$ – user593746 Nov 23 '18 at 11:26
  • $\begingroup$ The problem is taken from Ivan Niven number theory book. This might be a tipo though. $\endgroup$ – Maged Saeed Nov 23 '18 at 11:29
  • $\begingroup$ Since the statement is true if you use $a^{2^n}+1$, if you want a useful answer, maybe you should change the problem to $a^{2^n}+1$. $\endgroup$ – user593746 Nov 23 '18 at 11:32
  • $\begingroup$ @Zvi, consider the edited version of the post. $\endgroup$ – Maged Saeed Nov 23 '18 at 11:37
  • 2
    $\begingroup$ There is no typo in the text. It's problem 17 in Chapter 2, Section 8, and it concerns $a^{2^n}+1$, not $a^{2n}+1$. $\endgroup$ – Gerry Myerson Nov 23 '18 at 11:50

Let $p>2$ be a prime number such that $p \mid a^{2^n}+1$ for some integers $a$ and $n\geq 0$. We claim that $p\equiv 1\pmod{2^{n+1}}$. Clearly, $p\nmid a$, so $a^{p-1}\equiv 1\pmod{p}$ by Fermat's Little Theorem.

Let $k$ be the order of $a$ modulo $p$. Then, we have $k\mid p-1$. Since $a^{2^n}\equiv -1\pmod{p}$, we get $$a^{2^{n+1}} =\left(a^{2^n}\right)^2\equiv (-1)^2=1\pmod{p},$$ we conclude that $k\mid 2^{n+1}$. This shows that $k=2^m$ for some integer $m$ such that $0\leq m\leq n+1$.

Note that $m$ must equal $n+1$. If $m\leq n$, then $a^{2^m}\equiv 1\pmod{p}$, so that $$a^{2^n}=\left(a^{2^{m}}\right)^{2^{m-n}}\equiv 1^{2^{m-n}}=1\pmod{p}.$$ This means $1\equiv a^{2^n}\equiv-1\pmod{p}$, so $p\mid 2$, but this contradicts the hypothesis that $p>2$. Thus, $m=n+1$ and $k=2^{n+1}$. Recall that $k\mid p-1$, so $2^{n+1}\mid p-1$ and the proof is finished.

  • $\begingroup$ Thanks for this detailed answer. $\endgroup$ – Maged Saeed Nov 23 '18 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.