Practice Midterm Solutions

1. a) 4=gcd(4,12) does not divide 22, so the congruence has no solutions.

b)

$$3x + 15 \equiv 0 (mod 33)$$

Here 3=gcd(3,33) does divide 15, and so the congruence is equivalent to

$$x + 5 \equiv 0 (mod 11)$$

Thus $x \equiv 6 (mod 11)$. mod 33, the solutions are 6, 17, 28.

2. The system

$$4x + 11 \equiv 3 (mod 18)$$

$$6x + 9 \equiv 33 (mod 45)$$

Is equivalent to the system,

$$2x \equiv -4 (mod 9)$$

$$2x \equiv 8 (mod 15)$$

Which is equivalent to

$$x \equiv 7 (mod 9)$$

$$x \equiv 4 (mod 15)$$

Here 3=gcd(9,15) divides 7-4, so the system will have a solution unique mod lcm(9,15)=45. By inspection, 34 is a solution (mod 45). Thus, all solutions are of the form $34 + 45k, k \in \mathbb{Z}$.

3. Fermat's Little Theorem tells us that $x^{11} \equiv x (mod 11)$, so $x^{22} \equiv x^2 (mod 11)$, thus mod 11, the equation reduces to

$$2x +2 \equiv 0 (mod 11)$$

which has solution $x \equiv 10 (mod 11)$.

4. We use Hensel's lemma. Let's start with

$$2x^2 - x + 14 \equiv 0 (mod 5)$$

which has solutions $x \equiv 1, 2 (mod 5)$. Checking the derivative 4x - 1, we see that it does not vanish on either solution. Therefore, we will have two solutions (mod 5²) and (mod 5³). To get the solutions (mod 5²), we use the formula

$$s' = s - (f'(s))^{*} \times \frac{f(s)}{5} \times 5$$

For s=1, $s' = 1 - (3)^{*} \times 3 \times 5 \equiv 21 (mod 25)$, and for s=2, $s' = 2 - (2)^{*} \times 4 \times 5 \equiv 17 (mod 25)$. Finally, these solutions mod 5² must be lifted to solutions mod 5³. When s=21, we get $s'=21 - (3)^{*} \times \frac{875}{25} \times 25 \equiv 21 (mod 125)$. When s=17, we get $s'=17 - (2)^{*} \times \frac{575}{25} \times 25 \equiv 42 (mod 125)$

5. Schumer Q. 7, p. 58
Observe that p^m-1 for any prime p has this property.

{6. Schumer Q. 3, p. 62
Suppose that f(1)=0. Then $f(m)=f(m \times 1)=f(m)f(1)=0$, so that f would be identically 0, which is not allowed in the definition of a mult. function. Now $f(1)=f(1 \times 1)=f(1)^{2}$, and dividing both sides by f(1) we get f(1)=1.