On page 2 of the paper PRIMES is in P the following notation is used $$ (X + a)^n = X^n + a \hspace{4mm} (\text{mod } \hspace{2mm} X^r - 1, \hspace{2mm} n) $$ I am familiar with what $a = b \hspace{3mm} (\text{mod } c)$ means, but have never seen something of the form $a = b \hspace{3mm} (\text{mod } c, d)$ written. Can someone please tell me what this means?

  • 2
    $\begingroup$ The notation is explained in the first paragraph of page 3 of the paper. Kind of odd that they use it before defining it, I would say. $\endgroup$ – saulspatz Feb 22 '18 at 21:29
  • $\begingroup$ Ah, I should have read further before asking this question. Thanks. $\endgroup$ – M Smith Feb 22 '18 at 21:36
  • $\begingroup$ The referee or editor should have caught that and asked the author of the paper to put the def'n first. $\endgroup$ – DanielWainfleet Feb 24 '18 at 2:34

It means that you mod out by both $X^r - 1$ and $n$, at the same time. So for instance $X^r \equiv 1 \equiv nX + 1$ all at the same time.

In the ideal sense, you are working modulo the ideal $(X^r - 1, n)$, i.e. the ideal generated by $X^r - 1$ and $n$. Alternate representations could be $$ \mathbb{Z}[X] / (X^r - 1, n) \cong (\mathbb{Z}/n\mathbb{Z}) [X] / (X^r - 1).$$ This is defined in their 3rd section on notation --- the reason why they feel comfortable using this notation in the introduction is because it's fairly standard in ring theory (though admittedly it looks very familiar to those acquainted with congruences from elementary number theory).


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.