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.

  • 1
    $\begingroup$ The answer is yes, and it's immediate once you know that there exist primitive roots modulo any prime. $\endgroup$ – Wojowu May 20 at 20:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Greg Martin May 20 at 21:29
  • $\begingroup$ Apologies for the typo in the question title, but thank you! $\endgroup$ – Cisco Ortega May 21 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.