Prove that if $k\ge 1\,$ and $\,a^k\equiv 1\pmod{\! n}$ then $\gcd(a,n)=1$ 
Let $p$ be a prime such that $a^p-1 \equiv 0 \pmod{p}$. Prove that $\gcd(a,p) = 1$.

We know from Fermat's Little Theorem that $a^{p-1}-1 \equiv 0 \pmod{p}$ if and only if $\gcd(a,p) = 1$, but how do we use this to solve the question?
 A: Assume that $\gcd(a,p) \neq 1$. That is assume that $p$ divides $a$. That is, there is a $m$ such that $a = mp$. Then 
$$
a^{p} - 1 = (mp)^p - 1 = m^pp^p - 1 \equiv -1 \pmod{p}.
$$
A: That's a bit of an odd question, but if you really want to know this:  
As you remarked correctly $a^{p-1} -1 \equiv 0 \pmod{p}$ for $\gcd(a,p)=1$. 
It follows that $a^{p} -a \equiv 0 \pmod{p}$ for those $a$.  And if $\gcd(a,p)\neq 1$ then it is $p$ and thus $a^{p} -a \equiv 0 \pmod{p}$ also in that case as $a$ itself is $0 \pmod{p}$. 
Thus $a^{p}-a \equiv 0 \pmod{p}$ for all $a$. Hence $a^{p}-1 \equiv 0 \pmod{p}$ if and only if $a-1 \equiv 0 \pmod{p}$ that is $a \equiv 1 \pmod{p}$. This implies in particular that $\gcd(a,p)=1$.
(It's possible that the question was intended with $p-1$ instead of $p$, but then that's part of Fermat little theorem, so you know it anyway.)
A: Even more is true:

If $a$ and $b$ are integers and $n\in\mathbb N^+$ such that $a^n-1\equiv 0\pmod b$, then $\gcd(a,b)=1$.

What you want is then the special case where $n$ and $b$ both happen to equal the same prime.
Proof. $a^n-1\equiv 0 \pmod b$ means that there is $k$ such that $a^n-1=kb$ which is the same as $a^{n-1}a+(-k)b=1$, so by Bezout's identity $\gcd(a,b)$ must be $1$.
A: I hope the bar notation could make it an easier matter:
In the field $\mathbb{Z}/p\mathbb{Z}$, the equation $a^p-1\equiv 0 \pmod{ p}$ simply means
$\displaystyle\left(\overline{a}\right)^p=\overline{1}$.
And $\gcd(a,p)=1$ if and only if $\overline{a}\neq\overline{0}$, which is quite obvious from the above equation.
A: Um, don't let memorizing theorems make you lose your common sense. 
If $p$ is prime the only numbers not relatively prime to it are multiples of $p$ and $(kp)^p \equiv 0 \mod p$.
=======
A far stronger result would be $ma -1 \equiv \mod p \implies \gcd(a,p) = 1$ regardless of whether $p$ is prime or not or whether $m = a^{p-1}$ or any number.
Oh, and duh! If $a^p = 1 \mod p$ then $a \equiv 1 \mod p$.  That is a much more interesting and less trivial question.
A: It is a special case of the general fact that $\,a\,$ invertible mod $\,n\,$ implies $\,\gcd(a,n)= 1.\,$ Indeed, $\,aj\equiv 1\pmod{n}\,\Rightarrow\, aj+kn = 1\ $ so $\ d\mid a,n\Rightarrow\, d\mid 1,\,$ therefore $\,\gcd(a,n) = 1$.
OP is a special case since $\,{\rm mod}\ p\!:\  a^p-1\equiv 0\, \Rightarrow a(a^{p-1})\equiv 1\,$ so $\,a\,$ is invertible mod $\,p.$
Remark $\ $ The converse is also true, i.e. $\,\gcd(a,n) = 1\,\Rightarrow\,a\,$ is invertible mod $\,n,\,$ since by the Bezout identity for the gcd $\, \gcd(a,n) = 1\,\Rightarrow\, aj+kn = 1\,$ for some integers $\,j,k.\,$ Reducing this equation mod $\,n\,$ we obtain the congruence $\,aj\equiv 1\pmod n,\,$ i.e. $\,a^{-1}\equiv j\pmod n$
That fact that $\ a\,$ is invertible mod $\,n\iff \gcd(a,n)= 1\ $ is  fundamental and ubiquitous in elementary number theory, so one should be sure to be intimately familiar with it.
