Modular arithmetic notation - meaning of multiple arguments - $y \pmod{a,b}$

162 Views Asked by At

I understand Modular arithmetic with one argument eg $y \pmod{a}$.

I have two questions re this notation with multiple arguments - what is the meaning of the following and how to calculate them:

  1. $y \pmod{a,b}$ where $y$, $a$, $b$ are positive integers? Eg $14 \pmod{3, 7}$

  2. $y \pmod{a,b}$ where $b$ is a positive integer, and $a$ and $y$ are different polynomials / Quotient rings? Eg $x^5+3 \pmod{x^2-1, 7}$

Eg in AKS primality test - Wikipedia:

if $(X+a)^n≠ X^n+a \pmod {X^r − 1, n}$, output composite;

https://en.m.wikipedia.org/wiki/AKS_primality_test

1

There are 1 best solutions below

2
On

You just needed to read ahead another couple of lines on the page in question in order to find out what the notation means:

$$ (x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,n}}$$

means

$$ (x+a)^{n}-(x^{n}+a)=(x^{r}-1)g+nf \quad \text{for some polynomials $f$ and $g.$} $$

The explanation was probably thought to be necessary since this is not a typical notation.