# Thread: two elementary number theory problem:

1. ## two elementary number theory problem:

problem 1:
show that for every positive integer $n$, 7 divides $3^{2n+1}+2^{n+2}$

problem 2:
show that if $n$ is any odd integer greater than 1 ,then $n^{5}-n$ is divisible by 80

2. Problem 2, as you have it written, is incorrect. For example, for n=2, $n^5-n=2^5-2=32-2=30$,
and for n=4,
$n^5-n=4^5-4=1024-4=1020$,
neither of which is divisible by 80.
Now, if you consider odd n greater that 1...

--Kevin C.

3. thank you!
sorry! for writing the question incorrect.i have edited the question :-)

4. Hello, earthboy!

$\text{[1] Show that for every positive integer }n\text{, 7 divides }3^{2n+1}+2^{n+2}$

We have: / $3^{2n+1} + 2^{n+2} \;\;=\;\;3\cdot3^{2n} + 2^2\cdot 2^n \;\;=\;\;3(3^2)^n + 4(2^n)$

. . . . . . $=\;3\cdot9^n + 4\cdot2^n \;\;=\;\;3\cdot(7+2)^n + 4\cdot2^n$

. . . . . . $=\;3\bigg(7^n + {n\choose1}7^{n-1}\!\cdot\!2 + {n\choose2}7^{n-2}\!\cdot\!2^2 + \hdots + {n\choose1}7\!\cdot\!2^{n-1} + 2^n\bigg) + 4\!\cdot\!2^n$

. . . . . . $=\;3\bigg(7^n + {n\choose1}7^{n-1}\!\cdot\!2 + {n\choose2}7^{n-2}\!\cdot\!2^2 + \hdots + {n\choose1}7\!\cdot\!2^{n-1}\bigg) + 3\!\cdot\!2^n + 4\!\cdot\!2^n$

. . . . . . $=\;3\bigg(7^n + {n\choose1}7^{n-1}\!\cdot\!2 + {n\choose2}7^{n-2}\!\cdot\!2^2 + \hdots + {n\choose1}7\!\cdot\!2^{n-1}\bigg) + 7\!\cdot\!2^n$

. . . . . . $=\;3\!\cdot\!7\bigg(7^{n-1} + {n\choose1}7^{n-2}\!\cdot\!2 + {n\choose2}7^{n-3}\!\cdot\!2^2 + \hdots + {n\choose1}2^{n-1}\bigg) + 7\!\cdot\!2^n$

. . . . . . $=\;7\!\cdot\!\bigg[3\bigg(7^{n-1} + {n\choose1}7^{n-2}\!\cdot\!2 + {n\choose2}7^{n-3}\!\cdot\!2^2 + \hdots + {n\choose1}2^{n-1}\bigg) + 2^n\bigg]$

There!

5. Originally Posted by Soroban

We have: / $3^{2n+1} + 2^{n+2} \;\;=\;\;3\cdot3^{2n} + 2^2\cdot 2^n \;\;=\;\;3(3^2)^n + 4(2^n)$

. . . . . . $=\;3\cdot9^n + 4\cdot2^n \ldots$
It's a bit easier if you use congruence arithmetic starting from this point

$3\cdot9^n+4\cdot2^n\equiv3\cdot2^n+4\cdot2^n\equiv 7\cdot2^n\equiv0\pmod{7}$

6. Originally Posted by earthboy
problem 2:
show that if $n$ is any odd integer greater than 1 ,then $n^{5}-n$ is divisible by 80

Here's one thoughtless but valid approach

Pari/GP:
Code:
for(i=1,79,if(i%2==1&&(i^5-i)%80!=0,print(i)))
In fact the restriction "greater than 1" is unnecessary.

7. When n = 2k -1 for some integer, $n^5 - n$ can be written as $(2k-1)(4k^2 + 4k + 2)(2k)(2k-2)$. The last three factors are even and 4 divides either 2k or 2k-2. So 16 divides the product. If 5 does not divide any among 2k-1 and 2k-2 and 2k, then it must leave remainder 2 or 3 when it divides n. The second factor is $(n^2 + 1)$. If n=5m+2 or 5m+3, then $(n^2 + 1)$ is $25m^2 + 20m + 5$ and $25m^2 + 30m + 10$ respectively.

8. problem 2:
show that if n is any odd integer greater than 1 ,then $n^5-n$ is divisible by 80
Actually in a more closer look $n^5-n$ is divisible by 240 (for any odd n).

9. Or a proof by induction on n: when n= 0, $3^{2n+1}+ 2^{n+2}= 3^1+ 2^2= 3+ 4= 7$ which is divisible by 7.

Assume that, for some k, $3^{2k+1}+ 2^{k+2}$ is divisible by 7. That is, $3^{2k+1}+ 2^{k+2}= 7j$ for some integer j.

Then $3^{2(k+1)+ 1}+ 2^{(k+1)+ 2}= 3^{2k+ 1+ 2}+ 2^{k+2+ 1}= 9(3^{2k+1})+ 2(2^{k+1})$ $= 2(3^{2k+1}+ 2^{2k+1}+ 7(3^{2k+1})= 2(7j)+ 7(3^{2k+1})= 7(2j+ 3^{2k+1})$ is divisible by 7.

By induction on n, then, $3^{2k+1}+ 2^{k+ 2}$ is divisible by 7 for all n.