Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am proving that $$5n^3 + 7n^5 \equiv 0 \pmod{12}$$ It would suffice to show $$n^3 \equiv n^5 \pmod{12}$$ How would I go about doing that?

I suppose I could just go through each $n \equiv r \pmod{12}$ with $r$ from $1$ to $11$ and show that $n^3 \equiv n^5 \pmod{12}$ for each, but that would be tedious. Surely there's a better way.

share|cite|improve this question
up vote 11 down vote accepted

We need to show $$12|n^5-n^3$$ for each $n$. Factor this as $$n^3(n-1)(n+1).$$ This quantity will always be divisible by 3 (why?) and will always be divisible by 4 (why?) so it is divisible by 12.

Hint: If I have three consecutive integers one is divisible by 3.

Hint: If $n$ is even then we are done. If $n$ is odd both $n+1$ and $n-1$ are divisible by 2.

Remark: By this exact reasoning we actually get $24|n^5-n^3$ for each $n$.

share|cite|improve this answer
Do you care to explain why $24 | n^5 - n^3$ for odd n? – Covi Mar 12 '11 at 13:00
For odd $n$, both $(n-1)$ and $(n+1)$ will be even, and one of them will be a multiple 4. Thus $(n-1)(n+1)$ is a multiple of 8. – I. J. Kennedy Mar 12 '11 at 22:48
  • $n^2 = 0,1,4$ or $9 \mod 12$ by checking each number $0,1,2,3,4,5,6$ (we don't have to check $7,8,9,10$ and $11$ since they are negatives and $x^2 = (-x)^2).$
  • $n^4 = (n^2)^2 = n^2 \mod 12$ by checking each number 0,1,4 and 9.
  • thus $n^3 = n^5.$
share|cite|improve this answer
Much quicker, thank you. – Johan Feb 27 '11 at 23:24

It's just case $\rm\ p^j = 2^2,\ q^k = 3,\ d = e = 2\ $ of this simple generalization of Euler's little theorem

THEOREM $\ $ For primes $\rm\:p \ne q\:,\:$ naturals $\rm\:e\:$ and $\rm\ j,\ k \:\le\: d\ $

$$\rm\quad\quad\ \phi(p^j),\ \phi(q^k)\ |\ e\ \ \Rightarrow\ \ p^j\ q^k\ |\ n^d\ (n^e - 1)\ \ \ \forall\ n\in \mathbb N $$

Proof $\ $ If $\rm\ p\ |\ n\ $ then $\rm\ p^j\ |\ n^d\ $ by $\rm\ j\le d\:.\:$ Else $\rm\:n\:$ is coprime to $\rm\: p\:,\:$ so by Euler's little theorem we have: $\ $ mod $\rm\ p^j\:,\ \ n^{\phi(p^j)}\equiv 1\ \Rightarrow\ n^e\equiv 1\ $ by $\rm\ \phi(p^j)\ |\ e\:.\ $ Thus $\rm\ n^d\ (n^e - 1)\ $ is divisible by $\rm\ p^j\ $ and, similarly it is divisible by $\rm\ q^k\:,\ $ hence it is also divisible by their lcm = product. $\quad$ QED

In fact for $\rm\ p = 2,\ j > 2\ $ we can use $\rm\ \phi(2^j)/2\ $ vs. $\rm\ \phi(2^j)\ $ because $\rm\ \mathbb Z/2^j\ $ has multiplicative group $\rm\ C(2)\times C(2^{j-2})\ $ for $\rm\ j> 2\:$. Thus, in fact, $\rm\ 24\ |\ n^3\ (n^2 - 1)\:.$ For more see my post on the Fermat-Euler-Carmichael theorem.

share|cite|improve this answer
Again, the fact that this is more general does not imply my answer was bad. That technique of splitting into cases will solve a large number of congruence type problems for lower level courses. – Eric Naslund Feb 28 '11 at 16:15

$$\begin{align}n^5-n^3&=(n-2)(n-1)n(n+1)(n+2)-4n^3+4n\\\\ &=(n-2)(n-1)n(n+1)(n+2)-4(n-1)n(n+1)\end{align}$$

The first expression is a product of 5 consecutive numbers, hence is divisible by $5!$ i.e., by 120. Similarly, the second expression is divisible by $4\cdot (3!)$ i.e., by 24.

Also, $n^5-n^3 = n^2(n-1)n(n+1)$. Clearly, a product of 3 consecutive numbers $(n-1)n(n+1)$ is divisible by 3. Again, $n^5-n^3 = n^3(n^2-1)$.

If $n$ is even, the R.H.S. is divisible by 8. If $n$ is odd (equals to $2m+1$, say), then $$n^2-1 = (2m+1)^2 - 1 = 8m(m+1)/2$$ i.e, is divisible by 8 (See If $n$ is an odd natural number, then $8$ divides $n^{2}-1$).

share|cite|improve this answer
Please see here and here for how to format your mathematics expressions with LaTeX, and see here for how to use Markdown formatting. If you need to format more advanced math, there are many excellent LaTeX references on the internet, including StackExchange's own TeX.SE site. If you see a piece of LaTeX you want to know the code for on the site, you can right click on it, go to "Show Math As", then choose "TeX Commands". – Zev Chonoles Jun 9 '12 at 16:24

Your Answer


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.