Prime factor $p$ of $10^{2^k}+ 1$ is $p \equiv 1 \pmod{2^{k+1}}$

2018-05-13 16:12:51

I am asked to show that for when $n$ is a power of 2, any prime factor $p$ of $10^n + 1$ is $p \equiv 1 \pmod { 2n}$.

For $n = 1$, we have $p = 10^1 +1 = 11 \equiv 1 \pmod 2$

For $n > 1$ we now have that $10^n \equiv -1 \pmod{p}$ so $-1$ is a quadratic residue $\pmod p$ hence $ p \equiv 1 \pmod 4 \Rightarrow p \equiv 1 + 4l \pmod{2n}$ for some $0 \leq l < \frac{n}{2}$

Additionally, we have that $2n \mid 10^n \Rightarrow 10^n + 1 \equiv 1 \pmod{2n}$

I don't quite know how to conclude now that $p \equiv 1 \pmod{2n}$, I can't quite see why that would be true.

$10^{2^k} \equiv -1 \bmod p$ implies that the order of $10$ mod $p$ is $2^{k+1}$.

By Fermat, $10^{2^{k+1}} \equiv 1 \bmod p$, and so $2^{k+1}$ divides $p-1$.

  • $10^{2^k} \equiv -1 \bmod p$ implies that the order of $10$ mod $p$ is $2^{k+1}$.

    By Fermat, $10^{2^{k+1}} \equiv 1 \bmod p$, and so $2^{k+1}$ divides $p-1$.

    2018-05-13 16:39:46