76 73 67 bytes
f=lambda n,k=1:1-any(a**-~k*~-a**k%n for a in range(n))or-~f(n,k+1)
Try it online!
A further byte could be saved by returning True instead of 1.
Using the same approach, there is also the following implementation by @feersum which doesn't use list comprehensions.
f=lambda n,k=1,a=1:a/n or(a**-~k*~-a**k%n<1)*f(n,k,a+1)or-~f(n,k+1)
Note that this implementation requires O(nλ(n)) time. Efficiency could be improved dramatically while actually decreasing score to 66 bytes, but the function would return True for input 2.
f=lambda n,k=1,a=1:a/n or~-a**k*a**-~k%n<1==f(n,k,a+1)or-~f(n,k+1)
Definitions and notation
All employed variables will denote integers; n, k, and α will denote positive integers; and p will denote a positive prime.
a | b if b is divisible by a, i.e., if there is q such that b = qa.
a ≡ b (mod m) if a and b have the same residue modulo m, i.e., if m | a - b.
λ(n) is the smallest k such that ak ≡ 1 (mod n) – i.e., such that n | ak - 1 – for all a that are coprime to n.
f(n) is the smallest k such that a2k+1 ≡ ak+1 (mod n) – i.e., such that n | ak+1(ak - 1) – for all a.
λ(n) ≤ f(n)
Fix n and let a be coprime to n.
By the definition of f, n | af(n)+1(af(n) - 1). Since a and n do not have a common prime factor, neither do af(n)+1 and n, which implies that n | af(n) - 1.
Since λ(n) is the smallest integer k such that n | ak - 1 for all integers a that are coprime to n, it follows that λ(n) ≤ f(n).
λ(n) = f(n)
Since we've already established the inequality λ(n) ≤ f(n), it is sufficient to verify that k = λ(n) satisfies the condition that defines f, i.e., that n | aλ(n)+1(aλ(n) - 1) for all a. For this purpose, we'll establish that pα | aλ(n)+1(aλ(n) - 1) whenever pα | n.
λ(k) | λ(n) whenever k | n (source), so (aλ(k) - 1)(aλ(n)-λ(k) + aλ(n)-2λ(k) + ⋯ + aλ(k) + 1) = aλ(n) - 1 and, therefore, aλ(k) - 1 | aλ(n) - 1 | aλ(n)+1(aλ(n) - 1).
If a and pα are coprime, by the definition of λ and the above, pα | aλ(pα) - 1 | aλ(n)+1(aλ(n) - 1) follows, as desired.
If a = 0, then aλ(n)+1(aλ(n) - 1) = 0, which is divisible by all integers.
Finally, we must consider the case where a and pα have a common prime factor. Since p is prime, this implies that p | a. Carmichael's theorem establishes that λ(pα) = (p - 1)pα - 1 if p > 2 or α < 3 and that λ(pα) = pα - 2 otherwise. In all cases, λ(pα) ≥ pα - 2 ≥ 2α - 2 > α - 2.
Therefore, λ(n) + 1 ≥ λ(pα) + 1 > α - 1, so λ(n) + 1 ≥ α and pα | pλ(n)+1 | aλ(n)+1 | aλ(n)+1(aλ(n) - 1). This completes the proof.
How it works
While the definitions of f(n) and λ(n) consider all possible values of a, it is sufficient to test those that lie in [0, ..., n - 1].
When f(n, k) is called, it computes ak+1(ak - 1) % n for all values of a in that range, which is 0 if and only if n | ak+1(ak - 1).
If all computed residues are zero, k = λ(n) and
any returns False, so f(n, k) returns 1.
On the other hand, while k < λ(n),
1-any(...) will return 0, so f is called recursively with an incremented value of k. The leading
-~ increments the return value of f(n, k + 1), so we add 1 to f(n, λ(n)) = 1 once for every integer in [1, ..., λ(n) - 1]. The final result is thus λ(n).