7
$\begingroup$

I'm trying to prove that $30|a^{25}-a$.

First of all I said that it equals $a(a^3-1)(a^3+1)(a^6+1)(a^{12}+1)$, so that it must be divisible by 2.

Now I want to show it can be divided by $3,6$ using Fermat's little theorem.

I need a bit of direction since I'm kind of lost.

$\endgroup$
6
$\begingroup$

You need divisibility by $2,3,5$.

$a$ and $a^3-1$ are of different parity, so one of them is odd, one is even. Thie product is of course even.

$a^3\equiv a\pmod{3}$, so one of numbers $a^3-1$, $a$, $a^3+1$ is always divisible by $3$.

Now, for $5$.

  • The case $5|a$ is trivial.

  • $a\equiv 1\pmod{5}\implies a^3\equiv 1\pmod{5}\implies 5|a^3-1$

  • $a\equiv 2\pmod{5}\implies a^6+1\equiv 65\equiv 0\pmod{5}\implies 5|a^6+1$

  • $a\equiv 3\pmod{5}\implies a^6\equiv 9^3\equiv (-1)^3\equiv -1\pmod{5}\implies 5|a^6+1$

  • $a\equiv 4\pmod{5}\implies a\equiv -1\pmod{5}\implies a^3\equiv -1\pmod{5}\implies 5|a^3+1$

$\endgroup$
  • $\begingroup$ It seems to be more productive to appeal to Fermat's little theorem for the modulo-5-case of $x\not\equiv 0$ since $25\equiv 1\pmod{\varphi(5)}$. Then the same reasoning also works without change modulo 2 and 3. $\endgroup$ – Henning Makholm Nov 18 '17 at 12:33
3
$\begingroup$

Hint. By Fermat's little theorem, for any prime $p$, $a^{p}-a$ is divisible by $p$. Moreover, the polynomial $P(a)=a^{25}-a$ is divisible by $(a^r-a)$ for $r=2,3,5$.

$\endgroup$
2
$\begingroup$

As $(a^n-a)$ divides $a^{25}-a$ for $n=2,3,5,7,13$. For Little Fermat Theorem we know that $p$ divides $a^p-a$ for primes $p$, so $a^{25}-a$ is divisible by $2730$ for any integer $a>1$

Hope this helps

$\endgroup$
1
$\begingroup$

Since nobody mentioned Euler theorem here is another answer.

If $\gcd(a,30)=1$ then $a^{\varphi(30)} \equiv 1 \pmod{30}$ and $\varphi(30)=8$. Or $30 \mid a^8-1$ and $a^{25}-a=a(a^{24}-1)=a(a^8-1)(a^{16}+a^8+1)$. Thus $30 \mid a\cdot(a^{24}-1)$

If $\gcd(a,30)=d \in \{2,3,5,6,10,15,30\}$ then

  • $d=30$ then $30 \mid a \Rightarrow 30 \mid a\cdot (a^{24}-1)$
  • in all the other cases $30=d\cdot d_1$, $d \mid a$ and $\gcd(d_1,a)=1$ then $$a^{\varphi(d_1)} \equiv 1 \pmod{d_1} \tag{1}$$ or $30=d\cdot d_1 \mid a\cdot (a^{\varphi(d_1)}-1)$. But $d_1 \in \{2,3,5,6,10,15\}$ as well and $\varphi(2)=1,\varphi(3)=2,\varphi(5)=4, \varphi(6)=2, \varphi(10)=4, \varphi(15)=8$ all are factors of $24$. Or $24=\varphi(d_1)\cdot q$ and from $(1)$ $$a^{24}\equiv a^{\varphi(d_1)\cdot q} \equiv 1^{q} \equiv 1 \pmod{d_1}$$ Thus $30=d\cdot d_1 \mid a\cdot (a^{24}-1)$ too.
$\endgroup$
1
$\begingroup$

Perhaps a direct proof would be to express the Chinese remainder theorem as an isomorphism of rings $\mathbf Z/30 \cong \mathbf Z/2 \times \mathbf Z/3 \times \mathbf Z/5$. Write $[a_{30}]=([a_2], [a_3], [a_5])$ (obvious notation) and apply FLT to the 3 factors, using $25 = 1+2^3.3 = 1+ 3.2^3 = 5^2$, so that $[a_2]^{25}=[a_2].([a_2]^8)^3=[a_2].[a_2]^3=[a_2]$, and $[a_3]^{25}=[a_3].([a_3]^3)^8=[a_3]^9=[a_3]$, and $[a_5]^{25}=([a_5]^5)^5=[a_5]$ .

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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