# Prove that $2730$ divides $n^{13} - n$ for all integers $n$. [duplicate]

Prove that $2730$ divides $n^{13} - n$ for all integers $n$.

What I attempted is breaking $2730$ into $2, 3, 5$, and $7, 13$. Thus if I prove each prime factor divides by $n^{13} - n$ for all integers $n$, it will prove the original problem.

I already proved $2, 3$, and $5$ work. Struggling with how to do $91$?

Other solutions are welcome, but they should be associated with mod and solutions of this kind, because my answer should pertain to what was learned in class.

(Edit: Fixed the 91 problem, being slow today...In any case, I've got this problem now, so no answers are necessary. Posting my own soon.)

• You certainly want this the other way round.
– quid
Aug 6, 2015 at 22:35
• I think you mean find all integers $n$ such that ${n}^{13}-n$ is divisible by 2730 Aug 6, 2015 at 22:35
• Note that $91=7\cdot 13$. Then use Fermat's Theorem. Aug 6, 2015 at 22:36
• @mathflair The notation $2730|n^{13}-n$ means that $2730$ divides $n^{13}-n$, not that 2730 is divisible by $n^{13}-n$. Aug 6, 2015 at 22:38
• Right, Casteels. Sorry. Wasn't thinking when I typed it up--read Oussama's comment and that's not what I meant. I do mean prove that 2730 divides n^13 - n. Aug 6, 2015 at 22:44

$\phi(2),\phi(3),\phi(5),\phi(7)$ and $\phi(13)$ all divide $\phi(13)=12$, hence for any prime $p\in\{2,3,5,7,13\}$ we have: $$n^{13}\equiv n\pmod{p}$$ and that implies $2\cdot 3\cdot 5\cdot 7\cdot 13\mid (n^{13}-n)$.

• If the OP is really 14 years old, she probably doesn't know what $\phi$ means... Aug 7, 2015 at 8:17

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

Let's consider two cases:

First case:

if n is divisible by 2730 then $n\equiv 0[2730]$ so ${ n }^{ 13 }\equiv 0[2730]$ which means ${ n }^{ 13 }\equiv n[2730]$.

Second case $\gcd(2730,n)=1$:

Then all the prime divisors of $2730$ will be coprime with n.

Using Fermat little's theorem for $2, 3,5, 7, 13$:

$${ n }\equiv 1[2]\longrightarrow { n }^{ 12 }\equiv 1[2]\\ { { n }^{ 2 } }\equiv 1[3]\longrightarrow { n }^{ 12 }\equiv 1[3]\\ { { n }^{ 4 } }\equiv 1[5]\longrightarrow { n }^{ 12 }\equiv 1[5]\\ { { n }^{ 6 } }\equiv 1[7]\longrightarrow { n }^{ 12 }\equiv 1[7]\\ { { n }^{ 12 } }\equiv 1[13]\longrightarrow { n }^{ 12 }\equiv 1[13]\\$$

Which yields: $2730|{ n }^{ 12 }-1$ so:

$${ n }^{ 12 }\equiv 1[2730]\longrightarrow { n }^{ 13 }\equiv n[2730]\\ \qquad \qquad \qquad \longrightarrow \quad 2730|{ n }^{ 13 }-n$$

Third case $d = \gcd(n,2730)\quad \neq 1$:

In this case $n = d\alpha$ and $2730 = dq$

So:

$$n\equiv n[2730]\\ d\alpha \equiv d\alpha [dq]\\ \alpha \equiv \alpha [q]$$

And you apply the same method I did in the previous cases.

Hence proved for all n ^^.

Note:

For all primes ${ p }_{ 1 },{ p }_{ 2 },{ p }_{ 3 },...{ p }_{ m }$:

${ p }_{ 1 }|n,\quad { p }_{ 2 }|n,\quad { p }_{ 3 }|n,\quad ...{ p }_{ m }|n\Longleftrightarrow { p }_{ 1 }{ p }_{ 2 }...{ p }_{ m }|n$

• Your two cases most certainly don't cover all $n$ - for instance, they don't cover $25$... Aug 6, 2015 at 23:00
• Not sure if his solution is perfect, but it's the closest to the approach I'm trying to take--which is take the prime factors of 2730 and prove that n^13 - n is divisible by each, hence proving it for 2730. Aug 6, 2015 at 23:05
• I forgot the case where n and 2730 aren't coprime ^^ Aug 6, 2015 at 23:22

As pointed out in a comment $91$ is not prime but the product of $7$ and $13$. You can then deal with these two as you likely dealt with the other factors, via using Fermat's Little Theorem.

Let $k>1$ be an integer. Write $D(k)$ for the set of all prime natural numbers $p$ such that $p-1$ divides $k-1$. Then, $\displaystyle\underset{n\in\mathbb{N}}{\gcd}\left(n^k-n\right)$ is the product $\prod_{p \in D(k)}\,p$.

Let $d_k$ be the number $\displaystyle\underset{n\in\mathbb{N}}{\gcd}\left(n^k-n\right)$. Clearly, $d_k$ is squarefree (otherwise, if a prime $q$ satisfies $q^2\mid d_k$, then $q^2\mid d_k\mid q^k-q$, which is a contradiction). Now, we shall find which prime numbers can divide $d_k$.

Suppose a prime $p\mid d_k$. Then, $n^k\equiv n\pmod{p}$ for all $n\in\mathbb{N}$. Hence, $p-1$ must divide $k-1$ (otherwise, we can take $n$ to be a primitive element modulo $p$). That is, $p\in D(k)$.

On the other hand, if a prime $p$ is such that $p-1$ divides $k-1$, then we have $n^k=n\cdot n^{k-1}\equiv n\cdot 1=n\pmod{p}$ if $p\nmid n$, and $n^k\equiv 0\equiv n\pmod{p}$ if $p\mid n$. Hence, if $p\in D(k)$, then $p\mid d_k$.

This problem is only a particular case where $k=13$. Note that $$\prod_{p\in D(13)}\,p=2\cdot 3\cdot 5\cdot 7\cdot 13=2730\,.$$

• You need $k>1$ or else $q^2\mid d_k\mid q^k-q$ does not lead to a contradiction Aug 7, 2015 at 6:28
• This follows from Korselt's Criterion for Carmichael numbers. Jul 5, 2016 at 19:25