8
$\begingroup$

Show that $2730\mid n^{13}-n,\;\;\forall n\in\mathbb{N}$

I tried, $2730=13\cdot5\cdot7\cdot3\cdot2$

We have $13\mid n^{13}-n$, by Fermat's Little Theorem.

We have $2\mid n^{13}-n$, by if $n$ even then $n^{13}-n$ too is even; if $n$ is odd $n^{13}-n$ is odd.

And the numbers $5$ and $7$, how to proceed?

$\endgroup$
  • 1
    $\begingroup$ It seems like a factorization of $n^{13}-n$ should do it. $\endgroup$ – user99680 Dec 6 '13 at 21:12
  • $\begingroup$ See also math.stackexchange.com/questions/1387239/… $\endgroup$ – Martin Sleziak Aug 7 '15 at 10:03
  • $\begingroup$ By FLT $5|n^5 - n$ , $7|n^7 - n$ and $3|n^3 - n$. $n^13 - n = n(n^12 - 1) = n(n^6 + 1)(n^6 - 1) = n(n^6+1)(n^3 + 1)(n^3 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n^2 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n+1) (n-1)$. $n^7 - n = n(n^6 - 1)$ is a factor. $n^3 -n = n(n^2 - 1)$ is a factor. 5? well if $n = i \mod 5$ if i = 0 5|n if i = 1 5|n - 1. If i = 4 5|n+1. If i = 2 or 3 5|n^6+1. $\endgroup$ – fleablood Jul 5 '16 at 19:33

10 Answers 10

6
$\begingroup$

Like user99680,

Using Fermat's Little Theorem $p|(n^p-n)$ where $n$ is any integer and $p$ is any prime

$\displaystyle n^{13}-n=n(n^{12}-1)=n\left((n^6)^2-1\right)=n(n^6-1)(n^6+1)=(n^7-n)(n^6+1)$ which is divisible by $\displaystyle n^7-n$ which is always divisible by $7$ for all integer $n$

Similarly, $\displaystyle n^{13}-n=n(n^{12}-1)=n\left((n^4)^3-1\right)$ $\displaystyle=n(n^4-1)(n^8+n^4+1)=(n^5-n)(n^8+n^4+1)$ which is divisible by $\displaystyle n^5-n$ which is always divisible by $5$ for all integer $n$

$\endgroup$
  • $\begingroup$ You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$ $\endgroup$ – PM 2Ring Aug 7 '15 at 10:29
10
$\begingroup$

HINT:

$$n^{13} \equiv n^5 \cdot n^5 \cdot n^3 \equiv n \cdot n \cdot n^3 \equiv n^5 \equiv n \pmod 5$$

$$n^{13} \equiv n^6 \cdot n^7 \equiv n \pmod 7$$

Also you've missed $3$ as prime factor. But that should be easy.

$\endgroup$
5
$\begingroup$

One Approach

If $k\mid n$, then $x^{k+1}-x\mid x^{n+1}-x$. Therefore, $$ \begin{array}{} 13&\mid&n^{13}-n\\ 7&\mid&n^7-n&\mid&n^{13}-n&\text{since }6\mid12\\ 5&\mid&n^5-n&\mid&n^{13}-n&\text{since }4\mid12\\ 3&\mid&n^3-n&\mid&n^{13}-n&\text{since }2\mid12\\ 2&\mid&n^2-n&\mid&n^{13}-n&\text{since }1\mid12\\ \end{array} $$ Since the factors are all relatively prime, we have that $$ 2730=2\cdot3\cdot5\cdot7\cdot 13\mid n^{13}-n $$


Another Approach

Decomposing into a sum of combinatorial polynomials $$ \begin{align} n^{13}-n &=2730\left[\vphantom{\binom{n}{2}}\right.3\binom{n}{2}+575\binom{n}{3}+22264\binom{n}{4}+330044\binom{n}{5}\\ &+2458368\binom{n}{6}+10551552\binom{n}{7}+28055808\binom{n}{8}+47786112\binom{n}{9}\\ &+52272000\binom{n}{10}+35544960\binom{n}{11}+13685760\binom{n}{12}+2280960\binom{n}{13}\left.\vphantom{\binom{n}{2}}\right]\\ \end{align} $$

$\endgroup$
  • 3
    $\begingroup$ Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it. $\endgroup$ – Lubin Aug 7 '15 at 12:06
  • $\begingroup$ Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $\binom{n}{0}$. Evaluating $n^{13}-n-c_0\binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $\binom{n}{1}$. Evaluating $n^{13}-n-c_0\binom{n}{0}-c_1\binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $\binom{n}{2}$. etc. Other than the large numbers, it is pretty simple. $\endgroup$ – robjohn Aug 7 '15 at 12:34
4
$\begingroup$

Notice that $n^{13}-n =n(n^{12}-1)=n(n^6+1)(n^6-1)=n(n^6+1)(n^3+1)(n^3-1)=...$

$\endgroup$
3
$\begingroup$

Note that $$n^{13} \equiv n^5 \cdot n^5 \cdot n^3 \equiv n \cdot n \cdot n^3 \equiv n^5 \equiv n \pmod 5 \equiv n^{13} \equiv n^6 \cdot n^7 \equiv n \pmod 7.$$

$\endgroup$
3
$\begingroup$

$\, n = 2730 = 2\cdot 3\cdot 5\cdot 7\cdot 13 = \,$ product of all primes $\rm \,p\,$ such that $\rm \ \color{#c00}{p\!-\!1\mid 13\!-\!1}.\,$ Now apply

Theorem $\ $ For natural numbers $\rm\:a,e,n\:$ with $\rm\:e,n>1$

$\qquad\rm n\:|\:a^{\large e}-a\:$ for all $\rm\:a\:\iff n\:$ is squarefree, and prime $\rm\:p\:|\:n\,\Rightarrow\, \color{#c00}{p\!-\!1\mid e\!-\!1}$

Proof $\ $ See this answer for a short simple proof.

$\endgroup$
2
$\begingroup$

$2730 = 2\cdot 3\cdot 5\cdot 7\cdot 13$

The Carmichael function or least universal exponent function is composed by least common multiple over prime components, so $\lambda(2730) = \text{lcm}(\lambda(2), \lambda(3), \lambda(5), \lambda(7), \lambda(13)) = \text{lcm}(1,2,4,6,12)=12$. Note also that $2730$ is square-free, so the exponent cycle will be entered by the first power ($n^1$) for all numbers. Of course numbers coprime to $2730$ enter the cycle at the zeroth power ($1$).

Thus(!) $n^{(1+12)}\equiv n^1 \bmod 2730$ as required.

$\endgroup$
1
$\begingroup$

Cute corollary to FLT.

If $p,q $ are primes and $p-1=m|q-1=k$ then

$p|n^p -n=n (n^m-1)|n (n^m-1)(n^{k-m} + n^{k - 2m}+...+n^m+1)=n (n^k-1)=n^q-n $.

So as $1,2,3,4,6,12$ all divide $12$, it follows $2,3,5,7,13$ all divide $n^{13}- n $.

For me personally it was hardest to see that 5 did but $n^{13}-n = (n^8 + n^4 + 1)(n^5- n) $ so ... it does.

$\endgroup$
0
$\begingroup$

You can find the Chinese remainder theorem very useful.

$\endgroup$
0
$\begingroup$

Here is some way of automating Rob John's method:

You can always use decomposition over polynomials :$\quad\displaystyle \Pi_k(n)=k!\binom nk=\prod\limits_{i=0}^{k-1} (n-i)$

e.g. $\ \Pi_4(n)=(n-3)(n-2)(n-1)n$

To solve problems of the type: "show $m$ divides the polynomial $P(n)$"

Let have a look at a simpler example using this technique :

Prove $(n^5-n)$ is divisible by 5 by induction.

Though for $n^{13}-n$ it is a bit tedious.

Here is a maple procedure to do it:

> binomexpansion :=proc(P)
local a,b,c,d,i,p,q:
p:=P: d:= degree(P):
printf("%a = ",P):
for i from d to 0 by -1 do
a:=coeff(p,n,i):
q:=expand(binomial(n,i)):
b:=coeff(q,n,i):
c:=a/b:
p:=p-c*q:
if((c>0)and(i<d)) then printf("+"); fi:
if(c<>0) then printf("%d(n,%d)",c,i); fi:
end do: printf("\n"):
end proc

> binomexpansion(n^13-n);

n^13-n = 6227020800(n,13)+37362124800(n,12)+97037740800(n,11)+142702560000(n,10)+
         130456085760(n,9)+76592355840(n,8)+28805736960(n,7)+6711344640(n,6)+
         901020120(n,5)+60780720(n,4)+1569750(n,3)+8190(n,2)

You can notice that all coefficients are divisible by $2730=2.3.5.7.13$.

And since the binomial coefficients are integers, you get the divisibility by $2730$ as a result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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