Given that $\mathrm{hcf}(84,30)=6$, find $\mathrm{lcm}(84,30)$.

1. (i)

   Find the smallest positive integer $n$ such that $n\equiv 237\bmod 54$.

2. (ii)

   Find the largest negative integer $m$ such that $m\equiv 2391\bmod 142$.

1. (i)

   Find the highest common factor and the lowest common multiple of $45$ and $237$, and write the highest common factor as an integral linear combination of $45$ and $237$.

2. (ii)

   For each of the following three congruences, determine whether or not it has solutions; if solutions exist, find the complete solution:

   $$\text{(a)}\quad 45x\equiv 54\bmod 237;\qquad\text{(b)}\quad 45x\equiv 237\bmod 54;\qquad\text{(c)}\quad 237x\equiv 54\bmod 45.$$

Apply the Self-Explanation strategy from Appendix C to the proof of Theorem 4.7.1.

Given that $\mathrm{hcf}(1176,363)=3$, explain why the pair of congruences

have no simultaneous solutions.

1. (i)

   Show that the numbers $5$ and $12$ are coprime, and write $1$ as an integral linear combination of them.

2. (ii)

   Use the Chinese Remainder Theorem to find the complete solution to the pair of congruences

   $$x\equiv 3\bmod 5\qquad\text{and}\qquad x\equiv 9\bmod 12;$$

   that is, find all integers $x$ which satisfy the two congruences simultaneously.

1. (i)

   State the prime factorizations of $1176$ and $363$.

2. (ii)

   Find the highest common factor and the lowest common multiple of $1176$ and $363$.

3. (iii)

   Determine how many positive factors $1176$ and $363$ have.

A certain private school has fewer than $100$ pupils. They are allocated into teams of eight for rowing and eleven for hockey. Six are left over and get out of rowing; similarly four get out of hockey. How many pupils are there?

Suppose that the Sieve of Eratosthenes is applied to find all primes up to $10\,000$; so firstly multiples of $2$ are crossed out, secondly multiples of $3$, thirdly multiples of $5$ and so on. How many times would it be necessary to go through the grid crossing out multiples in this way?

For each of the following four congruences, determine whether or not it has solutions; if solutions exist, find the complete solution.

Use the Chinese Remainder Theorem to find the complete solution to the pair of congruences $x\equiv 36\bmod 217$ and $x\equiv 48\bmod 247$.

Apply the Self-Explanation strategy from Appendix C to the proofs of:
(i) Euclid’s Lemma (Theorem 4.4.8); (ii) Theorem 4.5.5; and (iii) Theorem 5.2.2.

Prove that there are infinitely many primes of the form $4n+3$.
[Hint: mimic the proof of Theorem 4.7.1; suppose that $p_{1},p_{2},\ldots,p_{k}$ are the only primes of this form, and consider $N=4p_{1}p_{2}\cdots p_{k}-1$.]

1. (i)

   Use Corollary 4.7.5 to prove that a natural number $n$ has an odd number of positive factors if and only if $n$ is a square.

2. (ii)

   Prove the result stated in (i) without using prime factorization.
   [Hint: pair together numbers whose product is $n$.]

(6 points) For each of the following two congruences, decide whether it has solutions; if solutions exist, find the complete solution:

(4 points) The first-year maths students at a certain university are divided into workshop groups of $15$ each and computer lab groups of $28$ each. One group is always filled up completely before a new group is created. One year, the final workshop group has $7$ students in it, while the final computer lab group consists of $13$ students only. It is known that less than $500$ first-year students study mathematics. How many such students are there exactly?

(Prime factorization) Find the prime factorizations of $4320$ and $2652$, and hence determine: (i) the highest common factor $d$ of $4320$ and $2652$; (ii) the lowest common multiple $\ell$ of $4320$ and $2652$; and (iii) the number $m$ of positive factors of $4320$. Then decide which one of the following five statements is true:

1. (A)

   $d=12$, $\ell=954\,720$ and $m=48$;

2. (B)

   $d=12$, $\ell=954\,720$ and $m=24$;

3. (C)

   $d=6$, $\ell=1\,909\,440$ and $m=48$;

4. (D)

   $d=6$, $\ell=1\,909\,440$ and $m=24$;

5. (E)

   $d=1$, $\ell=11\,456\,640$ and $m=24$.

(Existence of solutions to congruences) Decide which one of the following five statements is true:

1. (A)

   all three congruences

   $$28x\equiv 49\bmod 84,\qquad 28x\equiv 54\bmod 84\qquad\text{and}\qquad 28x\equiv 63\bmod 84$$

   have solutions;

2. (B)

   none of the three congruences above have solutions;

3. (C)

   the congruences $28x\equiv 49\bmod 84$ and $28x\equiv 54\bmod 84$ both have solutions, but the congruence $28x\equiv 63\bmod 84$ does not;

4. (D)

   the congruences $28x\equiv 49\bmod 84$ and $28x\equiv 63\bmod 84$ both have solutions, but the congruence $28x\equiv 54\bmod 84$ does not;

5. (E)

   the congruence $28x\equiv 54\bmod 84$ has solutions, but the congruences $28x\equiv 49\bmod 84$ and $28x\equiv 63\bmod 84$ do not.

(The complete solution to a congruence) Decide which one of the following five statements about the congruence $36x\equiv 111\bmod 339$ is true:

1. (A)

   no solutions exist;

2. (B)

   the complete solution is given by $x=-1739;$

3. (C)

   the complete solution is given by $x\equiv-1739\bmod 339;$

4. (D)

   the complete solution is given by $x\equiv 69\bmod 113;$

5. (E)

   the complete solution is given by $x\equiv 69\bmod 339.$

(Solving a pair of congruences I) For the pair of congruences

decide which one of the following five statements is true:

1. (A)

   no simultaneous solutions exist;

2. (B)

   the complete solution is given by $x\equiv 69\,513\bmod 173\,031;$

3. (C)

   the complete solution is given by $x\equiv 103\,620\bmod 173\,031;$

4. (D)

   the complete solution is given by $x\equiv 103\,620\bmod 346\,062;$

5. (E)

   none of the above.

(Solving a pair of congruences II) For the pair of congruences

decide which one of the following five statements is true:

1. (A)

   no simultaneous solutions exist;

2. (B)

   the complete solution is given by $x\equiv 16\bmod 20;$

3. (C)

   the complete solution is given by $x\equiv 396\bmod 240;$

4. (D)

   the complete solution is given by $x\equiv 504\bmod 2400;$

5. (E)

   none of the above.

(3 points)

1. (i)

   For $a,b\in\mathbb{N}$, show that if $b^{2}|a^{2}$, then $b|a$.
   [Hint: prime factorization.]

2. (ii)

   For each $n\in\mathbb{N}$, prove that either $\sqrt{n}\in\mathbb{N}$ or $\sqrt{n}\notin\mathbb{Q}$.

(3 points) Decide whether simultaneous solutions exist to the pair of congruences

If they do, find the complete solution.