7
$\begingroup$

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.

4 Answers 4

11

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

  • 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.2011-03-12
2
  • $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.$
  • 0
    Much quicker, thank you.2011-02-27
1

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.

  • 0
    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.2011-02-28
1

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

  • 0
    Please see [here](http://meta.math.stackexchange.com/a/464/264) and [here](http://meta.stackexchange.com/a/70559/161783) for how to format your mathematics expressions with LaTeX, and see [here](http://meta.stackoverflow.com/editing-help) 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](http://tex.stackexchange.com/) 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".2012-06-09