Past exam of the short options course of the University of Oxford / 2015 / 1

The binomial theorem isolates the only terms that can survive reduction modulo the prime number $p$:For $1\le r\le p-1$, neither $r!$ nor $(p-r)!$ is divisible by $p$, whereas $p!$ is. Consequently $p\mid \left(\genfrac{}{}{0ex}{}{p}{r}\right)$, and every intermediate term vanishes in modular arithmetic. ThusThis works for arbitrary integers $a,b$, including those divisible by $p$. It is the additive identity behind the Frobenius endomorphism in characteristic $p$.

For an odd prime number $p$, Euler's criterion states thatwhere the Legendre symbol is zero if $p\mid a$, one if $a$ is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer $a$.

Apply Euler's criterion to $a$, $b$, and $ab$. Multiplication in modular arithmetic givesIf $p$ divides either factor, both sides are zero. Otherwise both sides belong to $\{-1,1\}$; these two values are distinct modulo the odd prime number $p$. The congruence is therefore an equality of integers, proving multiplicativity of the Legendre symbol:

For distinct odd prime numbers $p,q$, the law of quadratic reciprocity isThus the two Legendre symbols agree unless both prime numbers are congruent to $3$ modulo $4$, in which case they have opposite signs.

In Pollard's p-1 algorithm, a large exponent containing many small factors makes $a^M-1$ divisible by a prime factor whose predecessor divides $M$, by Fermat's little theorem. A greatest common divisor with the number being factored can then separate that prime factor from the others.

Choose base $a=2$ and build factorial exponents using modular exponentiation. The successive exponents $2!$, $3!$, and $4!$ giveThe first two greatest common divisors are $\gcd (3,1003)=\gcd (63,1003)=1$. At the next step the Euclidean algorithm givesHenceHere the element order of $2$ modulo $17$ is $8$, which divides $24$, even though $17-1=16$ does not divide $24$. The algorithm only needs the element order to divide the chosen exponent; divisibility by the full predecessor is a sufficient condition, not a necessary one.

First simplify the specified residue by modular exponentiation. Modulo the prime number $113$,Therefore $102^{70}\equiv 28\cdot 64\cdot 8\equiv 98$, so the required equation becomes $x^{37}\equiv 97(\mathrm{mod}113)$. Its right side is nonzero, so any solution is a unit modulo $113$.

By Fermat's little theorem, exponents of such units can be reduced modulo $112$. Sinceraising to the $109$th power is the inverse of raising to the $37$th power. There is therefore exactly one residue class of solutions:Now $97\equiv -16$ and $97^3\equiv -4096\equiv 85$. Since $4\cdot 85\equiv 1$, we obtainAs a direct check, $4^4\equiv 30$, $4^8\equiv 109$, $4^{16}\equiv 16$, and $4^{32}\equiv 30$, whence $4^{37}\equiv 30\cdot 30\cdot 4\equiv 97$.