A necessary and sufficient condition for Carmichael numbers If $n$ is a positive integer and $(n,a)=1$ then $x = \phi(n)$ is a solution of the congruence $a^{x} \equiv 1 (\textrm{mod}\ n)$. However there could be one or more smaller exponents satisfying the above congruence for all $(n,a)=1$. E.g. if $\gcd(a,123) = 1$ then, $a^{40} \equiv 1 (\textrm{mod}\ 123)$. 
Clearly $40 < \phi(123) = 80$.
We denote by $l(n)$ the lowest exponent such that $a^{l(n)} \equiv 1 (\textrm{mod}\ n)$ for all $a$ satisfying $(n,a)=1$. Trivially $l(n) \le \phi(n)$. 
Claim: A composite integer $n$ is a Carmichael number iff $n \equiv 1 (\textrm{mod}\ l(n))$.
I am looking for a proof or disproof of the claim.
 A: This conjecture seems to fail, if $n$ is a prime number [this was allowed before you changed your question]. Since not composite, $n$ is not a Carmichael number. But on the other hand, the existence of primitive roots mod $n$ implies that $l(n) = n-1$, which leads to $n \equiv 1$ (mod $l(n)$).
But we may do the following: Let $n \in \mathbb{N}, n>1$. Then the following are equivalent: 
(i) For all $a \in \mathbb{N}, \gcd(a,n)=1$ we have $a^{n-1} \equiv 1$ (mod $n$).
(ii) $n \equiv 1$ (mod $l(n)$).  
Proof: (i) $\Longrightarrow$ (ii): For each $a \in \mathbb{N}, \gcd(a,n)=1$, we have $a^{n-1} \equiv 1$ (mod $n$) as well as $a^{l(n)} \equiv 1$ (mod $n$). Since $l(n)$ is the smallest positive number with that property, we conclude $l(n) \leq n-1$. Now we can find natural numbers $q,r$ such that $n-1 = l(n) \cdot q + r$ and $r < l(n)$. For all $a \in \mathbb{N}, \gcd(a,n)=1$ we find $1 \equiv a^{n-1} = a^{l(n) \cdot q + r} \equiv a^r$ (mod $n$) and (since $r < l(n)$) $r=0$ is the only possible choice for $r$. But this implies that $l(n) \mid n-1$, hence $n \equiv 1$ (mod $l(n)$).
(ii) $\Longrightarrow$ (i): There exists $k \in \mathbb{N}$, such that $n = 1 + k \cdot l(n)$. If $a \in \mathbb{N}, \gcd(a,n)=1$, we get 
$a^{n-1} = a^{k \cdot l(n)} = (a^{l(n)})^k \equiv 1^k = 1$ (mod $n$) by the definition of $l(n)$.
