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