2
$\begingroup$

I showed that $a^{15}-a^3=(a^5-a)$ so by Fermat's, $5|a^5-a$ so $5|a^{15}-a^3$. I also showed that $a^{15}-a^3=a^3(a^{12}-1)$ so by Euler, $a^{12}-1 \equiv 0$ mod 13.

I am having a hard time showing that 7 divides $a^{15}-a^3=(a^5-a)$. They talk about it some in this post but I am still not seeing it. Thank you.

$\endgroup$
  • $\begingroup$ What do you mean you showed $a^{15}-a^3=(a^5-a)$ ? $a^{15}-a^3\ne(a^5-a)$ $\endgroup$ – fleablood Feb 24 '17 at 1:59
7
$\begingroup$

The $5$ divisibility won't be relevant here. Just note that $a^{15}-a^3=a^{3}(a^{12}-1)$ as you did and if $7|a$ you are done, otherwise $a^6\equiv 1\mod 7$ by Fermat and so $a^{12}=(a^6)^2\equiv 1\mod 7$ so $a^{12}-1\equiv 0\mod 7$ as desired.

$\endgroup$
2
$\begingroup$

$a^{15}-a^3 = a^3(a^{12}-1) = a^3(a^6-1)(a^6+1)= (a^7-a)(a^9+a^3)$

$7|a^7-a$ by LFT

$\endgroup$
2
$\begingroup$

If $a\equiv 0\mod7$, it's obvious. If not, Lil' Fermat ensures $\;a^{15}\equiv a^3\mod7$.

$\endgroup$
2
$\begingroup$

In $mod \space 7$ $$\large{a^{\phi(7)}}\equiv 1 \\a^6 \equiv 1 \to \\{(a^6)}^2\equiv 1^2 $$now,multiply by $a^3$ $$a^{12} \equiv 1 \\\times a^3\\a^{12+3}\equiv1.a^3$$

$\endgroup$
2
$\begingroup$

You can prove it uniformly for all three primes as in the following Theorem, which implies that $\,5\cdot 7\cdot 13\mid a^{13}-a\,$ so also $\,a^2(a^{13}-a) = a^{15}-a^3$

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

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

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

$\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.