Past exam of the mathematics course of the University of Cambridge / 2015 / ia / Paper 4 / 1E (Numbers and Sets)

Subtracting twice the first linear congruence from the second gives $5x\equiv 1(\mathrm{mod}53)$. Since $5\cdot 32=3\cdot 53+1$, the modular inverse of $5$ modulo $53$ is $32$. Thus $x\equiv 32(\mathrm{mod}53)$. Substitution in the first linear congruence then gives $2y\equiv 23(\mathrm{mod}53)$, whence $y\equiv 38(\mathrm{mod}53)$. All integer solutions areThe two free integers are independent. Conversely, these values give $6x+2y\equiv 268\equiv 3$ and $17x+4y\equiv 696\equiv 7(\mathrm{mod}53)$, so no additional restriction is needed.

Write the composite number as $n=ab$, with $2\le a\le b<n$. If $a<b$, both $a$ and $b$ occur as distinct factors of the factorial $(n-1)!$, so their product $n$ divides that factorial.

If $a=b$, then $n=a^2$ and $n>4$ implies $a\ge 3$. Both $a$ and $2a$ are distinct factors in $(n-1)!$, because $2a\le a^2-1$. Their product is $2n$, so again $n$ divides the factorial. HenceThe exception $n=4$ matters: its factorial $3!=6$ is not divisible by $4$. This argument handles perfect squares without incorrectly counting the same factor twice.