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.

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|improve this question
    
Are these homework problems you have been posting? –  Aryabhata Feb 27 '11 at 23:19
    
Yes. Is that an issue? –  Johan Feb 27 '11 at 23:20
    
Not as long as you show what you have tried. –  Aryabhata Feb 27 '11 at 23:21
    
Edited in. Thanks for the advice. –  Johan Feb 27 '11 at 23:24
4  
Kindly tag them as homework in future. I have tagged this one. –  user17762 Feb 27 '11 at 23:27

4 Answers 4

up vote 9 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|improve this answer
    
Do you care to explain why $24 | n^5 - n^3$ for odd n? –  Covi Mar 12 '11 at 13:00
1  
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|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|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|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

 
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.