Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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