2
$\begingroup$

Prove that $a^5 ≡ a$ (mod 15) for every integer $a$

  • We are currently studying modular arithmetic and congruence and I came across this proof on my study set that I'm really not sure how to approach. We have gone over equivalence relations in mod arithmetic, equivalence classes (complete set of residues), and have gone through several mod arithmetic examples w/o variables. Looking through my notes and book I'm still not sure how to proceed with this problem, any help is appreciated.
$\endgroup$
  • 2
    $\begingroup$ It is sufficient to proof this for a=0,...,14 $\endgroup$ – miracle173 Feb 20 '16 at 20:00
  • $\begingroup$ Fermat's little theorem states $a^5 \equiv a \pmod 5$ maybe that helps somehow $\endgroup$ – George Feb 20 '16 at 20:00
  • $\begingroup$ $a^5 \equiv a\cdot a^4 \equiv a \pmod 5;$ $a^5 \equiv a^4 \cdot a \equiv (1)^2\cdot a \equiv a \pmod 3$. Chinese remender theorem. $\endgroup$ – L.F. Cavenaghi Feb 20 '16 at 20:00
  • $\begingroup$ By Fermat's Little Theorem $a^5\equiv a\pmod{5}$. Also $a^5-a=(a-1)a(a+1)\cdot \left(a^2+1\right)$ is divisible by $3$, because exactly one of $a-1,a,a+1$ is divisible by $3$. $\endgroup$ – user236182 Feb 20 '16 at 20:15
6
$\begingroup$

If $a\in{\mathbb Z}$ then $$c:==a^5-a=a(a-1)(a+1)(a^2+1)$$ is obviously divisible by $3$, and is obviously divisible by $5$ if $a\in\{-1,0,1\}\ {\rm mod}\ 5$. If $a=\pm2\ {\rm mod}\ 5$ then $a^2+1=0\ {\rm mod}\ 5$. It follows that $c=0\ {\rm mod}\ 15$ for all $a\in{\mathbb Z}$.

$\endgroup$
1
$\begingroup$

Observe that an integer $n$ satisfies $n \equiv 0 \pmod{15}$ if and only if $n \equiv 0 \pmod 3$ and $n \equiv 0 \pmod 5$. Therefore, it suffices to prove that $a^5 \equiv a \pmod 5$ and $a^5 \equiv a \pmod 3$. The first formula follows from Fermat's little theorem. For the second formula, it con for instance consider separately the three cases:

  1. if $a \equiv 0 \pmod 3$, then $a^5 \equiv 0 \pmod 3$,
  2. if $a \equiv 1 \pmod 3$, then $a^5 \equiv 1 \pmod 3$
  3. if $a \equiv -1 \pmod 3$, then $a^5 \equiv -1 \pmod 3$.
$\endgroup$
  • 1
    $\begingroup$ By Fermat's little theorem (all congruences are modulo $3$), $a^3\equiv a$, so $a^5\equiv a^3\equiv a$. No need to do cases. $\endgroup$ – egreg Feb 20 '16 at 20:34
1
$\begingroup$

Fermat little theorem:

$a^5 \equiv a \mod 5$ so $a^5 -a \equiv 0 \mod 5$.

If $3\not |a$, $a^2 \equiv 1 \mod 3$ so $a^5 \equiv a \mod 3$ so $a^5 -a \equiv 0 \mod 3$

So, $a^5 -a \equiv 0 \mod 15$.

Or... we could factor $a^5 - a = (a-1)a (a+1)(a^2+1) $. $3|(a-1)a (a+1)$ and $5|a^2 +1 \iff 5|a^2+5a+6=(a+2)(a+3) $ and $5|(a-1)a (a+1)(a+2)(a+3) $

$\endgroup$
  • $\begingroup$ $a^4\equiv 1\pmod{5}$ is true if and only if $5\nmid a$. Whereas $a^5\equiv a\pmod{5}$ is true for all $a\in\mathbb Z$. Both can be called Fermat's Little Theorem. $\endgroup$ – user236182 Feb 20 '16 at 20:35
  • $\begingroup$ Fermat's little theorem is $a^p\equiv a\pmod{p}$. $\endgroup$ – egreg Feb 20 '16 at 20:36
  • $\begingroup$ Gosh I was tired and don't like typing on my phone... $\endgroup$ – fleablood Feb 21 '16 at 0:45

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.