4
$\begingroup$

Prove that for all $a \in \mathbb{Z}$ we have $$ a^{25} \bmod 65 = a \bmod 65. $$

We have $65 = 5 \cdot 13$, where $5$ and $13$ are prime. So I wanted to compute the first expression by using the Chinese Remainder theorem. I have to find a $x$ which satisfies the system $$ \begin{cases} x \bmod 5 = a^{25} \bmod 5 \\ x \bmod 13 = a^{25} \bmod 13 \end{cases}. $$ But how can I solve this system when I don't know what $a$ is? I tried using Fermat's little theorem for the prime number $23$, but the above equation has to hold for all $a \in \mathbb{Z}$, not only with $gcd(a,p) = 1$.

So how can we solve this problem?

$\endgroup$
7
$\begingroup$

If $a=0$ then this is trivial, so assume $a\neq 0$.

$\mathbb{Z}_5=\mathbb{Z}/5\mathbb{Z}$ is a field, so $\mathbb{Z}_5^\times$, the group of invertible elements, is a group of $4$ elements.

In particular, we have $a^4\equiv 1\bmod 5$, so $a^{24}=(a^4)^6\equiv 1\bmod 5$, and $a^{25}\equiv a\bmod 5$.

Similarly, $\mathbb{Z}_{13}$ is a field, and its group of invertible elements has $12$ elements, so $a^{12}\equiv 1\bmod 13$, $a^{24}\equiv 1\bmod 13$, and thus $a^{25}\equiv a\bmod 13$.


Remark: You can avoid fields and use Fermat's little theorem directly: $$a^5\equiv a\bmod 5.\tag{5.1}$$ Taking the $5$-th power, we obtain $$a^{25}\equiv a^5\bmod 5\tag{5.2}$$ and putting $(5.1)$ and $(5.2)$ together, $$a^{25}\equiv a\bmod 5.$$ Now for $13$: $$a^{13}\equiv a\bmod{13}\tag{13.1}$$ Multiply by $a^{12}$: $$a^{25}\equiv a^{13}\bmod{13}\tag{13.2}$$ put $(13.1)$ and $(13.2)$ together: $$a^{25}\equiv a\bmod{13}.$$

$\endgroup$
  • $\begingroup$ Thanks for the reply. But how do know that $a^{5} \equiv a \bmod 5$? You use Fermat for this? Then we need to have the extra information that $gcd(a, 5) = 1$? $\endgroup$ – Kamil Aug 10 '16 at 18:03
  • $\begingroup$ @Kamil This is simply Fermat's little theorem: If $p$ is prime then $a^p\equiv a\bmod p$ for all $a\in\mathbb{Z}$:en.wikipedia.org/wiki/Fermat%27s_little_theorem $\endgroup$ – Luiz Cordeiro Aug 10 '16 at 18:11
1
$\begingroup$

The Chinese Remainder Theorem is rarely of any use when you're looking at variable expressions. But factoring $65$ as $5 \cdot 13$ is useful.

First, notice that there are $65$ possible combinations of $x \mod 5$ and $x \mod 13$; so each number $0$ through $64$ has a different such signature. By Fermat's little theorem, $a^5 \equiv a \mod 5$, so $a^{25} = (a^5)^5 \equiv a^5 \equiv a \mod 5$. Again by Fermat, $a^{13} \equiv a \mod 13$, so $a^{12} \equiv 1 \mod 13$ (unless $a \equiv 0 \mod 13$). Since $a^{25} = a \cdot (a^{12})^2$, either way we have $a^{25} \equiv a \mod 13$. So $a^{25}$ and $a$ have the same signature mod $5$ and $13$, and hence $a^{25} \equiv a \mod 65$.

$\endgroup$
  • $\begingroup$ $5$ is not equivalent to $0\bmod 65$, but $5^{24} \equiv 40\bmod 65$. $\endgroup$ – Luiz Cordeiro Aug 10 '16 at 17:28
  • $\begingroup$ Quite right, I missed that. Argument fixed, I believe. $\endgroup$ – Reese Aug 10 '16 at 17:45
1
$\begingroup$

Notice $\, n = 65 = 5\cdot 13 \,$ is a product of distinct primes $\rm \,p\,$ such that $\rm \ \color{#c00}{p\!-\!1\mid 25\!-\!1},\:$ thus

Theorem $\ $ For natural numbers $\rm\:a,e,n\:$ with $\rm\:e,n>1$

$\qquad\rm n\:|\:a^e-a\:$ for all $\rm\:a\:\iff n\:$ is squarefree, and prime $\rm\:p\:|\:n\,\Rightarrow\, \color{#c00}{p\!-\!1\mid e\!-\!1}$

Proof $\ (\Leftarrow)\ $ Hint: since a squarefree natural divides another iff all its prime factors do, we need only show $\rm\:p\:|\:a^e\!-\!a\:$ for each prime $\rm\:p\:|\:n,\:$ or, that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1} \equiv 1\pmod p,\:$ which, since $\rm\:p\!-\!1|\:e\!-\!1,\:$ follows from $\rm\:a \not\equiv 0\:$ $\Rightarrow$ $\rm\: a^{p-1} \equiv 1 \pmod p,\:$ by little Fermat.

$(\Rightarrow)\ $ Not needed here, see this answer

$\endgroup$

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.