E.7 Online-assessed exercises from week 3

Exercise 3.17. We have $4320=2^{5}\cdot 3^{3}\cdot 5$ and $2652=2^{2}\cdot 3\cdot 13\cdot 17$, where $2$, $3$, $5$, $13$ and $17$ are prime (as we showed using the Sieve of Eratosthenes in Section 4.6). Proposition 4.7.10 implies that

By Corollary 4.7.5, $4320$ has $m=(5+1)(3+1)(1+1)=6\cdot 4\cdot 2=48$ positive factors. Hence (A) is the correct answer.

Exercise 3.18. We have $\mathrm{hcf}(28,84)=28$ because $28|84$ (or because their prime factorizations are $28=2^{2}\cdot 7$ and $84=2^{2}\cdot 3\cdot 7$, or alternatively by the Euclidean algorithm), so Theorem 5.2.2 implies that:

• •

  the congruence $28x\equiv 49\bmod 84$ has no solutions because $28\!\!\!\!\;\not\!\!\!\;|\!\;49$;

• •

  the congruence $28x\equiv 54\bmod 84$ has no solutions because $28\!\!\!\!\;\not\!\!\!\;|\!\;54$;

• •

  the congruence $28x\equiv 63\bmod 84$ has no solutions because $28\!\!\!\!\;\not\!\!\!\;|\!\;63$.

Hence (B) is the correct answer.

Exercise 3.19. The highest common factor of $36$ and $339$ is $3$ because

As $3|111$, the congruence has solutions, and we can simplify it to $12x\equiv 37\bmod 113$, where $12$ and $113$ are coprime because $1=5\cdot 113-47\cdot 12$ (divide by $3$ in the integral linear combination found above). Hence the complete solution is given by

so that (D) is the correct answer.

Exercise 3.20. We use the Euclidean algorithm to show that $411$ and $421$ are coprime and to write $1$ as an integral linear combination of them:

Hence the Chinese Remainder Theorem (Theorem 5.3.2) applies; in the notation of this theorem, we have $a=48$, $b=54$, $m=411$, $n=421$, $r=42$ and $s=-41$, and the complete solution is given by

(Note that no further simplification is possible because $0\leqslant 103\,620<173\,031$.) Hence (C) is the correct answer.

Exercise 3.21. We have $\mathrm{hcf}(60,40)=20$ (because $20|60$ and $20|40$ and $20=60-40$, or by prime factorization), and $20$ does not divide $36-14=22$, so Proposition 5.3.5 implies that the two congruences cannot be solved simultaneously. Hence (A) is the correct answer.