# Describe in terms of congruence class all of the odd primes $p = 2m+1$ such that $p \mid 10^m - 1$

Describe in terms of congruence class all of the odd primes $p = 2m+1$ such that $p \mid10^m - 1$.

$p=2m+1 \iff 2m \equiv 1 \pmod p$

$p \mid 10^m - 1 \iff 10^m \equiv 1 \pmod p$

So, I have $2m = 10^m$ modulo $p$

1. Is the question asking for all the primes in the set described above?
2. What do I do next?
-

By Euler's Criterion, this is the case precisely if $10$ is a quadratic residue of $p$.

Now we can use Quadratic Reciprocity to solve the problem. Because the quadratic character of $2$ depends on the congruence class of $p$ mod $8$, and the quadratic character of $5$ depends on the congruence class of $p$ mod $5$, our answer will involve the congruence class of $p$ mod $40$.

I think that when the smoke clears, you should get that $p\equiv \pm 1$, $\pm 3$, $\pm 9$, or $\pm 13$ modulo $40$.

Added: The Legendre symbol $(10/p)$ is equal to $1$ if (i) both $(2/p)$ and $(5/p)$ are equal to $1$, or (ii) both are equal to $-1$.

For Case (i), we want $p\equiv\pm 1\pmod{8}$. Also, we want $(5/p)=1$. Since $5$ is of the form $4k+1$, by Reciprocity we want $(p/5)=1$. This is the case if $p\equiv \pm 1\pmod{5}$. Stitch together the congruences $p\equiv \pm 1\pmod{8}$ and $p\equiv \pm 1\pmod{5}$ using the Chinese Remainder Theorem (the numbers are small, so this can be done by inspection). We will get $4$ solutions modulo $40$.

Case (ii) is similar.

-
Could you quickly clarify for me why $10$ is a quadratic residue mod $p$? – CodeKingPlusPlus Oct 25 '12 at 17:16
Nevermind, it is a quadratic modulo $p$ by Euler's Criterion. – CodeKingPlusPlus Oct 25 '12 at 17:35