Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $n$ is an integer which is not divisor of 5. Prove that $n^4 \equiv 1 \pmod{5}$.

I tried saying that $n$ is not equal to 5 or 1, thus $n$ must divide $2 \times 3 \times 4 = 24$. I am stuck at this point.

share|improve this question
1  
As below posters have mentioned, you probably mean "divisible by 5" since integers that are not "divisors of 5" are just all integers except 1 and 5. –  Evan W Jul 19 at 0:33

10 Answers 10

I would approach this with a proof by cases. There are $5$ options for $n\pmod{5}$:

Case $n\equiv 0\pmod 5$: Not possible by assumption.

Case $n\equiv 1 \pmod 5$: In this case, note that $n^4\equiv 1^4 \equiv 1 \pmod 5$

Case $n\equiv 2 \pmod 5$: (keep going--it's similar...)

Case ...

EDIT: this does assume that you meant "divisible," not "a divisor."

share|improve this answer
    
Best proof in my opinion –  frogeyedpeas Jul 19 at 0:58
    
Yes. Finally someone who isn't beating this to death with F.L.T. +1 –  Rod Jul 19 at 18:50
    
I actually prefer the FLT method because it's extensible, but that may just be me. It just didn't jump out at me this time. :) –  anorton Jul 19 at 18:57

Fermat's little theorem states that if $p$ is prime, then for all $n$ with $\gcd(n,p)=1$, we have $$n^{p-1} \equiv 1 \mod p.$$ In your case we have $p=5$.

One proof: Because $\gcd(n,p)=1$ there is a number $m$ such that $nm \equiv 1 \mod p$. This means the map $f(x)=nx$ is a bijection on the set $\{1,2,\dots, p-1\}$ to itself since there is an inverse $f^{-1}(x)=mx$. Therefore,

$$1n \cdot 2 n\cdots (p-1)n = 1 \cdot 2 \cdots (p-1) \mod p$$

because the same set of numbers mod $p$ is being multiplied on each side. Rewrite

$$n^{p-1} (p-1)! \equiv (p-1)! \mod p$$

and cancel the $(p-1)!$ terms, which we can do because every number in $\{1,2,\dots, p-1\}$ is relatively prime to $p$ and has an inverse.

share|improve this answer
2  
Quite stellar. Only flaw is citing Wikipedia. Maybe I should go on Wikipedia right now and change that article to some utter nonsense, or better yet, put in some subtle mistake that could ensnare most novices. –  Robert Soupe Jul 20 at 3:21
1  
I've reveiwed the Wikipedia article and couldn't find any mistakes in it. But that's no guarantee their isn't some mistake I missed, or that it won't get changed to something incorrect. –  Albert Jul 21 at 21:16
1  
There's nothing wrong with wikipedia. The math articles are almost always useful. And if they are wrong, well isn't mathematics the queen of sciences because anyone can verify an argument? –  nayrb Jul 21 at 21:29
1  
@anorton Please note that I thought it was serious enough for me to comment but not serious enough for me to downvote. Maybe the math articles on Wikipedia are better than the history, politics and other such topics. But I just prefer to assume it's all wrong, the same way I assume all blue liquids are unsuitable to drink. If that puts me in a minority, oh well. I probably dislike Wikipedia for different reasons than math professors dislike Wikipedia. –  Robert Soupe Jul 22 at 4:01
1  
@anorton Thanks, I am interested in those two posts, I might forward them to the math professor who wrote a post for Wikipediocracy. –  Robert Soupe Jul 23 at 1:20

Fermat's little theorem provides an easy way.

But if you're not completely convinced, consider the squares modulo 5: $0, 1, 4, 4, 1$. Then the cubes: $0, 1, 3, 2, 4$. Then the fourth powers: $0, 1, 1, 1, 1$. Voila.

share|improve this answer

Hint

It suffices to consider the cases $n=1,2,3$ or $4$.

share|improve this answer
    
Nice and short hint! Lovely avatar Sami. God bless her. :+) –  Babak S. Jul 28 at 21:35

$$n^4-1=(n-1)(n+1)(n^2+1)$$

Since $\;n\neq0\pmod 5\;$, if it is $\;\pm1\pmod 5\;$ the above is $\;0\pmod 5\;$, and if it is $\;n=\pm 2\pmod 5\;$, then $\;n^2=(\pm2)^2=4\implies n^2+1=0\pmod 5\;$.

In any case, $\;n^4-1=0\pmod 5\;$

share|improve this answer

$$n \equiv \pm 1 \space\mathrm{or} \pm 2 \pmod 5$$

Hence

$$n^4 \equiv (\pm 1)^4 \space\mathrm{or} \space(\pm 2)^4 \pmod 5 \\ \implies n^4 \equiv 1 \space\mathrm{or} \space 16 \pmod 5 \\ \therefore n^4 \equiv 1 \pmod 5$$

share|improve this answer

Like Timbuc,

$$n^4-1=(n-1)(n+1)(n^2+1)=(n-1)(n+1)(n^2-4+5)$$

$$=\underbrace{(n-2)(n-1)(n+1)(n+2)}+5(n-1)(n+1)$$

As $n$ must divide exactly one of any five consecutive integers and $5\nmid n,(5,n)=1,$

$n$ must divide one of the multiplicand underbrace

share|improve this answer

Here's a group theoretic perspective. The set of positive integers smaller than and relatively prime to $5$ form a group under multiplication mod $5$. If $n$ is not divisible by $5$ then $n$ is not congruent to $0$ mod $5$. Thus working mod $5$ we have $n$ is congruent to one of $\{1,2,3,4\}$ which is precisely the group mentioned above. The order of this group is $4$, and as a corollary to lagrange's theorem any member of the group raised to the $4^{th}$ power must be the identity element, namely $1$. Hence $n^4 \equiv 1$ mod $5$.

share|improve this answer

Here's one particularly pretty way of proving this statement. It's nice because it uses combinatorics to prove an essentially number theoretic result. We start with the problem:

Suppose you want to make a necklace with $5$ beads, and you can paint each one of them with one of $n$ available colors. What's the number of different necklace you can have? (Necklace that can be obtained from other necklaces under rotation are considered the same)

We could stay that there are $n$ different ways to color the first bead, $n$ different ways to color the second, etcetera. But there are $5$ different rotations for each collar. Therefore the answer must be $\frac{n^5}{5}$, right? No, but close enough.

For instance, if all of the beads have only one color, then this necklace won't generate any other necklace under rotation. On the other hand, if a necklace has more than one color, then we affirm that it generates $5$ different necklaces (including itself). This is not an immediately obvious result so we shall prove it formally.

Indeed, let $(a_1,a_2,a_3,a_4,a_5)$ be a necklace, where $a_k$ is the color of the bead $k$. By assumption, there are $i,j \in \Bbb{Z}$ such that $a_i\neq a_j$ (consider the indices modulo $5$). Suppose we rotate the necklace by $r$ places. We affirm that $(a_1,a_2,...,a_5)=(a_{1+r},a_{2+r},...,a_{5+r})$ if and only if $r$ is a multiple of $5$. Suppose it's not, and $a_{i}=a_{i+r}$ for all $i$. Inductively, $a_i=a_{i+mr}$, for $m\in\Bbb{Z}$. But since we're looking at the indices modulo $5$, let $m=(j-i)\cdot r^{-1}$ where $r^{-1}$ is the inverse of $r$ modulo $5$ (it exists since $5$ is prime and $5\nmid r$). Then $a_i=a_{i+mr}=a_{i+(j-i)r^{-1}r}=a_j$ for all $i,j$. But we're assuming there are $i,j \in \Bbb{Z}$ such that $a_i\neq a_j$. Absurd.

Therefore the number of ways is actually $\frac{n^5-n}{5}+n$. The nice fact is that this number must be an integer (quite obviously), so in particular $\frac{n^5-n}{5}=\frac{n(n^4-1)}{5}$ is an integer. If $5\nmid n$, then $\gcd(5,n)=1$ since $5$ is prime, therefore $5\mid n^4-1\Rightarrow n^4\equiv 1 \pmod 5$. $\,\,\blacksquare$

share|improve this answer
    
You might notice that throughout the proof we never really used any information about the number $5$ that distinguishes it from every other number. We only used the fact that it is a prime number. So you can pretty much exchange $5$ for $p$ prime and you get a proof of Fermat's Little Theorem. –  Deathkamp Drone Jul 19 at 8:06

Also, you can prove that $5|n^5-n$ by induction on $n$ and from this conclude the claim.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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