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

For distinct odd primes $p,q$, quadratic reciprocity statesHere the Legendre symbol records whether a nonzero congruence class is a quadratic residue. The first supplementary law for quadratic reciprocity and second supplementary law for quadratic reciprocity giveThus minus one is a square exactly when $p\equiv 1(\mathrm{mod}4)$, and two is a square exactly when $p\equiv 1$ or $7(\mathrm{mod}8)$.

To test the specified congruence class, factor $111=3\cdot 37$. Since $2017\equiv 1(\mathrm{mod}4)$, multiplicativity of the Legendre symbol and quadratic reciprocity yieldThere is no sign change on swapping $19$ and $37$ because $37\equiv 1(\mathrm{mod}4)$. Finally $18=2\cdot 3^2$, so multiplicativity of the Legendre symbol gives $(18/19)=(2/19)=-1$, since $19\equiv 3(\mathrm{mod}8)$. Therefore

For an odd prime $p$, Euler's criterion statesFor $p\nmid a$, the Legendre symbol is $1$ for a quadratic residue and $-1$ for a quadratic nonresidue; if $p\mid a$, both sides are zero.

The product is a single power because the arithmetic progression of exponents has sum $2017\cdot 2018/2$:Since $2017\equiv 1(\mathrm{mod}8)$, the second supplementary law for quadratic reciprocity gives $(2/2017)=1$. Hence Euler's criterion gives $2^{1008}\equiv 1(\mathrm{mod}2017)$. Reduce the exponent using $1009=1008+1$ and $2017=2\cdot 1008+1$:The least nonnegative remainder is therefore $2$.

Euler's totient function counts the integers in a complete complete residue system that are coprime to the modulus:If the prime factorization is $n={\prod }_{j=1}^r{p}_j^{e_j}$ with distinct prime numbers $p_j$, Euler's totient product formula isIn particular, $\varphi (2017)=2016$. Adjoining the prime factor $2$ changes neither the odd factor nor its count of units, since $\varphi (2)=1$. The product formula givesThis is a positive integer distinct from $2017$, as required.

The Chinese remainder theorem says that for pairwise coprime positive moduli $m_1,\dots ,m_r$ and arbitrary integers $a_1,\dots ,a_r$, the simultaneous modular congruenceshave a solution, unique modulo $M={\prod }_i{m}_i$.

Choose $2017$ distinct prime numbers $q_1,\dots ,q_{2017}$. Their prime powers $q_i^{2017}$ are pairwise coprime. Apply the Chinese remainder theorem toFor the resulting integer $n$, each $n+i$ is divisible by $q_i^{2017}$, the required power of an integer greater than one. Adding a sufficiently large multiple of ${\prod }_i{q}_i^{2017}$ makes $n$ positive without changing any modular congruence. Thus such a positive $n$ exists, indeed infinitely many do. This is the general construction of consecutive integers divisible by prescribed prime powers.