Is it true that there is always an integer $a$ such that $n|a^n-1 $ Let $n$ be a positive integer such that $gcd(n,\phi (n)) \neq 1$.Is it true that there is always an integer $a$ such that $n|a^n-1 $ (with $1<a<n$, $a$ and $n$ are coprime) ? If not, what are the conditions of $n$ so that there exist such integer $a$ with $n|a^n-1 $ ?
I include $gcd(n,\phi (n)) \neq 1$ is because if $n|a^n-1 $ then $ord_n(a)|n$. We also have $ord_n(a)|\phi(n)$ and  $ord_n(a)>1$ since $1<a<n$ and $gcd(a,n)=1$. Thus $ord_n(a)|gcd(n,\phi (n))$ and $gcd(n,\phi (n)) \neq 1$.
 A: I believe the answer is "yes", and this is how I would prove it.
Suppose $n = p_1^{e_1}\dots p_J^{e_J} $ is the prime factorisation of $n$. Then 
$$ U_n \cong C_{\phi(p_1^{e_1})} \times \dots \times C_{\phi(p_J^{e_J})},$$
where $U_n$ denotes the group of units modulo $n$, and $C_{\phi(p_j^{e_j})}$ denotes a cyclic group of order $\phi(p_j^{e_j})$, and the $\cong$ symbol denotes a group isomorphism.
Since $\gcd(n, \phi(n)) \neq 1 $, there exists a prime number $q$ that divides both $n$ and $\phi(n)$. And since $$\phi(n) = \phi(p_1^{e_1}) \dots \phi(p_J^{e_J}),$$ it follows that  $q$ must divide $\phi(p_j^{e_j})$ for at least one $j \in \{ 1, \dots, J\}$. To keep my notation simple, I'll assume without loss of generality that
$$ q \ | \ \phi(p_1^{e_1}),$$
i.e. that there exists an integer $m$ such that
$$ \phi(p_1^{e_1}) = qm.$$ 
Now, for each $j \in \{1, \dots, J \}$, let $g_j$ denote a generator of the cyclic group $C_{\phi(p_j^{e_j})}$, and consider the element
$$ a := (g_1^m, 1, 1, \dots, 1) $$
in the group $U_n \cong C_{\phi(p_1^{e_1})} \times \dots \times C_{\phi(p_J^{e_J})}$.
Clearly, $ a$ is not the identity element in $U_n$, but $a^q$ is the identity element in $U_n$. (This is because $g_1^m$ is not the identity in $C_{\phi(p_1^{e_1})}$, but $g_1^{qm}$ is the identity in $C_{\phi(p_1^{e_1})}$.)
Any power of $a^q$ is therefore also equal to the identity element in $U_n$. In particular, since $q | n$, we have that $a^n$ is equal to the identity element in $U_n$, which completes the proof.

Note added: By the same method, we can prove the more general fact: if $k$ is an integer such that $\gcd (k, \phi(n)) \neq 1$, then there exists an element $a \in U_n$ such that $a \neq 1$ and $a^k = 1$ in $U_n$. Your result is the special case where $k = n$.
In fact, we can do even better: if $G$ is a finite abelian group, and $k$ is an integer such that $\gcd (k, |G|) \neq 1$, then there exists an element $g \in G$ such that $g \neq 1$ and $g^k = 1$ in $G$. This can also be proved in the same way, assuming that you know that every finite abelian group is isomorphic to a product of cyclic groups.
