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

The Euler theorem states that if $\gcd (a,d)=1$, thenLet $r_1,\dots ,r_{\varphi (d)}$ be the reduced residue classes modulo $d$. Multiplication by $a$ permutes them, soTheir product is a unit and may be cancelled, proving the theorem.

A decimal integer is congruent modulo $3$ to its digit sum. Cyclic permutation does not change that sum. Hence every rotation of a multiple of $3$ is again divisible by $3$.

Divisibility by $2$ or $5$ depends only on the final digit. As the digits are cyclically rotated, every digit appears in the final position. Thus every rotation is divisible by $d\in \{2,5\}$ exactly when every digit is divisible by $d$.

As printed, the claim is false: $70$ is 7-cyclic-divisible because its rotations are $70$ and $07=7$, but its digits are not all equal to $7$ and its length is not a multiple of $6$.

The standard rotation argument proves the likely intended statement. If an $L$-digit integer and all its rotations are divisible by $7$, then for each leading digit $a$,is divisible by $7$. The multiplicative order of $10$ modulo $7$ is $6$. If $6\nmid L$, then $7\nmid 10^L-1$, forcing every digit $a$ to be divisible by $7$, hence to be either $0$ or $7$. Thus the valid conclusion is:The counterexample shows why “all its digits are equal to 7” cannot replace the first alternative.

LetBy Fermat's little theorem, $l\mid p-1$. If the digit count $L$ is a multiple of $l$, then $10^L\equiv 1(\mathrm{mod}p)$. The cyclic decimal divisibility relation givesand hence also modulo $p$. Since $p>7$ is coprime to $10$, every $10^j$ is a unit modulo $p$. Thereforefor every $j$. Since $c_0(n)=n$, this proves the required equivalence.