Problem
NT-B2-M03-P014 General Fact for the Plus Sign
#14
★★★★☆ Level 4 of 5
Let \(p\) be an odd prime, \(p\nmid a\), and \(p\mid a^n+1\). Prove that \( \operatorname{ord}_p(a) \) divides \(2n\), but does not divide \(n\).
Translate the condition into \(a^n\equiv-1\pmod p\).
From \(p\mid a^n+1\), we get \(a^n\equiv-1\pmod p\). Then \(a^{2n}\equiv1\), so the order divides \(2n\). If the order divided \(n\), then \(a^n\equiv1\pmod p\), contradicting \(a^n\equiv-1\pmod p\), since \(p\) is odd.
This fact will be used repeatedly in \(a^n+1\) problems.