Why does gcd(a,n) have to be 1 for there to exist a $d$ such that $a^d \equiv 1 \pmod{n}$ In the definition for multiplicative order, one of the requirements is that the modulo and the base are coprime. That is, if there exists some order $d$ such that
$$a^d \equiv 1 \pmod{n}$$
then gcd(a,n) must be 1.

However, I do not understand why this must be true. Why cannot $a^d$ ever be congruent to $1$ modulo n if a is not relatively prime to n?
 A: This comes down to the fact that any sum of multiples of $a$ and $n$ is divisible by a common divisor. More precisely: if $a^d \equiv 1 (\mod n)$, then definitions imply that $a^d-xn=1$ for some integer $x$. Now, suppose $d$ is a common divisor of $a$ and $n$. Since $d|a$ and $d|n$, it follows that $d|(a^d-xn)$, which is impossible unless $d$ is $\pm1$.
In fact, a stronger statement is true: if $ab \equiv 1 (\mod n)$, then $\gcd(a,n)=1$ and $\gcd(b,n)=1$. It might be a useful exercise to adapt the above argument to prove this.
A: Hint $ $ note $\ {\rm mod}\ n\!:\ a\,$ invertible $\,\Rightarrow\,\gcd(a,n)=1,\ $ by $\  ab\equiv 1\,\Rightarrow\, \begin{eqnarray} \color{#0a0}ab\!+\!k\color{#0a0}n \,=\,\color{#c00}1 \\ d\mid \color{#0a0}{a,n}\Rightarrow d\mid \color{#c00}1\end{eqnarray}$

Conversely  $\,\ {\rm mod}\ n\!:\ a\,$ invertible $\iff \gcd(a,n) = 1,\ $
 by Bezout's identity for the gcd. 
Generally, $\ \ {\rm mod}\ n\!:\ a\,$ invertible $\iff a\mid \color{#c00}1,\ $  so it's special case $\,\color{#c00}{b=1}\,$ of
Theorem $\ \: {\rm mod}\: n\!:\,\ a\,\mid\,\color{#c00} b\iff \gcd(n,a)\mid\color{#c00} b\ $ in $\ \Bbb Z$
$\begin{eqnarray}{\bf Proof}\quad\ \ \,  &&\qquad\quad\ \,  a\,\mid\, b\!\pmod n\\
\iff&&\qquad\ \ \,  k\, a\equiv b\!\!\pmod n,\ \ {\rm for\ some}\ \ k \\
\iff&&  \ j\,n + k\,a = b,\ \ {\rm for\ some}\,\ j,k\\
\iff && {\rm gcd}(n,\,a)\,\mid\, b,\ \  {\rm by\ Bezout}
\end{eqnarray}$ 
A: Suppose that $\gcd(a,n) = k > 1$. Then, $k | a^d$ for all $d \in \mathbb N$, so $a^d \equiv 0 \pmod k$.
Then, as $k | n$, any multiple of $k$ is in one of the equivalence classes $0,k,2k,\dots,n - k $ modulo $n$, and since $k > 1$, none of these equivalence classes are $1 \pmod n$.
A: Based on @MorganO's answer, I think I came up with another way to prove this via proof by contradiction:
Assume that there exists non-relatively prime $a$ and $n$ such that
$$a^d \equiv 1 \pmod{n}$$
Then you have $$a^d = 1 + nk$$
Because $a$ and $n$ are not relatively prime, their gcd is not 1. Now reduce both sides by gcd(a,n).
$$0 \equiv 1 \pmod{gcd(a,n)}$$
Contradiction.
