# In general, do primes of the form $a×2^{n}+1$always have primitive $2^n$th roots of unity (modulo that prime)?

EDIT: Title had an extra +1 in the 2's exponent

For context, in competitive programming, problems which require a number theoretic transform usually ask for the answer modulo $$998244353=7\times17\times2^{23}+1$$, since this has a primitive $$2^{23}$$rd root of unity. I recently saw another problem that asks for the answer modulo $$1005060097=3^3\times71\times2^{19}+1$$, and it in fact does have a $$2^{19}$$th primitive root of unity.

I feel like this can't be a coincidence, though I can't quite put my finger on it.

• The answer is yes, and it's immediate once you know that there exist primitive roots modulo any prime. – Wojowu May 20 at 20:19
• Indeed, one can take @Wojowu's comment further: if $p$ is prime and $d$ is any divisor of $p-1$, then $p$ does have primitive $d$th roots of unity. – Greg Martin May 20 at 21:29
• Apologies for the typo in the question title, but thank you! – Cisco Ortega May 21 at 1:26