Prove that if $p\ge 7$ then $\exists n\in\Bbb{Z}$ such that $10^{n(p-1)}\equiv1 \mod 9p$. Edit: $p$ is prime, of course. I tried using theorems regarding Euler, but I can't seem to arrive at something useful. I could really use your guidance.
4 Answers
Note that $10$ and $9p$ are relatively prime, and that $\varphi(9p)=6(p-1)$. Now use Euler's Theorem.
Much more simply, we can take $n=0$. Indeed $10^t\equiv 1\pmod{9}$ for any $t$. So the congruence holds for any non-negative integer $n$.
-
$\begingroup$ If I wanted to show that for any $n$? Can I say that if $10^n\equiv 1 \mod 9$, then $10^{n(p-1)}\equiv 1^{p-1}\mod 9p$? What is the right way to derive it? $\endgroup$– MeitarMay 9, 2015 at 18:48
-
1$\begingroup$ We have $10^{n(p-1)}\equiv 1\pmod{9}$, since $10\equiv 1\pmod{9}$. We also have $10^{p-1}\equiv 1\pmod{p}$, by Fermat's Theorem, since $10$ and $p$ are relatively prime. So $10^{n(p-1)}=(10^{p-1})^n\equiv 1\pmod{p}$. Since $9$ and $p$ are relatively prime, it follows that $10^{n(p-1)}\equiv 1\pmod{9p}$. Of course $n$ has to be a non-negative integer, else $10^{n(p-1)}$ is not an integer. $\endgroup$ May 9, 2015 at 18:52
-
$\begingroup$ Do you have any idea why there is no reference to the condition $p\ge 7$? $\endgroup$– MeitarMay 9, 2015 at 18:58
-
1$\begingroup$ There is reference in what I wrote, several times. I used the fact that $10$ and $p$ are relatively prime when I used Fermat's Theorem, for the argument would fail if $p$ divides $10$, that is, if $p=2$ or $p=5$. I also used the fact that $9$ and $p$ are relatively prime in concluding from $10^{n(p-1)}\equiv 1\pmod{9}$ and $\pmod{p}$ that $10^{n(p-1)}\equiv 1\pmod{9p}$. And in the first line (Euler's Theorem proof), we need $10$ relatively prime to $p$. We also need $p\ne 3$ to see that $\varphi(9p)=6(p-1)$. But for a very formal writeup we should explicitly mention all these things. $\endgroup$ May 9, 2015 at 19:12
It is true for every $n$. Use Fermat's Little Theorem to show it is equivalent to $1\pmod9$ and $1\pmod p$.
Doesn't $n=6$ always work, since $(10,9p)=1$ and $\Phi(9p)=6(p-1)$?
By pigeon-hole, there exist $k,m$ with $10^{k(p-1)}\equiv 10^{m(p-1)}$ and wlog. $k>m$. Since $10$ is coprime to $9p$, we can cancel $10^{m(p-1)]}$ and find $10^{(k-m)(p-1)}\equiv 1\pmod{9p}$.