Question: > 
> 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.)

Answer: 
$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$
> 
> 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\,.$$