<s>[INST] Number theory congruence 
Prove that $n^{12} - a^{12}$ is divisible by $91$ if $n$ and $a$ are co prime to $91$

What I tried:


*

*$91$ divides $n^{12}-a^{12}$

*Therefore $n^{12}-a^{12}=91k$

*But $91=13\times7$

*$n^{12}-a^{12}=(13\times7)k$

*$n^{12}=(13\times7)k+a^{12}$

*$n^{12}$ divides $91$

*Therefore $n$ is co prime to $91$
 [/INST] Two things should leap to mind.  And a third thing comes with practice.
1) $91 = 13*7$ so to prove $91|M$ it will work to prove a) $7|M$ and b) $13|M$.  If you can prove a) and b) you are done.
2) $n^{12} - a^{12} = (n^6 - a^6)(n^6 + a^6) = (n^3 - a^3)(n^3 + a^3)(n^6 + a^6)=....$.  The expression $n^{12}-a^{12}$ is "very" factorable.  If we can prove that of the many factors that $7$ and/or $13$ must divide at least one of the factors that will help.  There are so many factors something working out is likely.
And with practice:
3) $12 = 13 -1$ and $13$ is prime.  So Euler's Theorem/Fermats Little Theorem will probably come into play.
.....
Factor $n^{12} -a^{12}$ completely.  
$n^{12}-a^{12} = (n-a)(n^11 + n^10a + .... +na^{11} + a^{12})=$
$(n^2 - a^2)(n^{10} + n^8a^2 + .... + n^2a^8 + a^{10})=$
$(n^3 - a^3)(n^9 + n^6a^3 + n^3a^6 + a^9)=$
$(n^4-a^4)(n^8 + n^4a^4 + a^8)=$
$(n^6 - a^6)(n^6 + a^6) =$
$(n^6+a^6)(n^3 + a^3)(n^2+a^2)(n+a)(n-a)$.
Those probably have different remainders when divided by $7$ or $13$.  One of them can probably be proven to be $0$. but... that may be hard to figure out.  Let's put a pin in it and look at 3)
3) Fermat's little theorem states if $\gcd(k,13)=1$ then $k^{12}\equiv 1 \pmod {13}$.  And $n,a$ are coprime to $91$ so they are coprime to $13$ so
$a^{12} \equiv 1 \pmod {13}$ and $n^{12} \equiv 1 \pmod {13}$ so $n^{12}-a^{12}\equiv 1-1 \equiv 0 \pmod 13$ so $13|(n^{12} - a^{12})$.
So now we just need to prove $7|n^{12} - a^{12}$....
Back to the factoring... oh, wait!....
Fermat's Little Theorem states $n^6\equiv 1\pmod 7$ and $a^6\equiv \pmod 7$ so $n^{12}-a^{12} = (n^6- a^6)(n^6 + a^6)\equiv (1-1)(n^6 + a^6)\equiv 0 \pmod 7$ so $7|n^{12}-a^{12}$.
And we are done!
We didn't need to do that factoring stuff at all. 
Still it'd be interesting to see if we can do it by considering just the factors.  But we don't have to.
</s>