## § Chapter 1 Review: Solved problems

1. Find gcd (7605, 5733), and express it as a linear combination of 7605 and 5733.

Solution: Use the matrix form of the Euclidean algorithm:

Thus gcd(7605, 5733) = 117, and 117 = (-3) · 7605 + (4) · 5733.

```

```
2. For , prove that n = 1 if and only if 3 | n, for any integer n.

Solution: An easy calculation with complex numbers shows that
, and 3 = 1. (The computations are also done in the introduction to Chapter 1 of the text.)

If n in Z, and 3 | n, then n = 3q for some q in Z, and n = 3q = (3)q = 1q = 1.

Conversely, if n in Z and n = 1, use the division algorithm to write
n = q · 3 + r, where the remainder satisfies 0 r < 3. Then
1 = n = 3q+r = (3)q r = r. Since r = 0,1,2 and we have shown that
1 and 2 1, the only possibility is r = 0, and therefore 3 | n.

```

```
3. Solve the congruence 24x 168 (mod 200).

Solution: First we find that gcd(24,200) = 8, and 8 | 168, so the congruence has a solution. The next step is to reduce the congruence by dividing each term by 8, which gives
24x 168 (mod 200). To solve the congruence
3x 21 (mod 25) we could find the multiplicative inverse of 3 modulo 25. Trial and error shows it to be -8, we can multiply both sides of the congruence by -8, and proceed with the solution.

24x 168 (mod 200)
3x 21 (mod 25)
-24x -168 (mod 25)
x 7 (mod 25)

The solution is x 7,32,57,82,107,132,157,182 (mod 200).

```

```
4. Solve the following system of congruences.

2x 9 (mod 15)     x 8 (mod 11).

Solution: Write x = 8 + 11q for some q in Z, and substitute to get
16 + 22q 9 (mod 15), which reduces to
7q -7 (mod 15), so
q -1 (mod 15). This gives
x -3 (mod 11 · 15).

```

```
5. List the elements of Z15×. For each element, find its multiplicative inverse, and find its multiplicative order.

Solution: There should be 8 elements since (15) = 8. By Problem 1.4.39, the multiplicative order of any nontrivial element is 2, 4, or 8. The elements are [1], [2], [4], [7], [8], [11], [13], and [14]. Computing powers, we have [2]2 = [4], [2]3 = [8], and [2]4 = [1]. This shows not only that the multiplicative order of [2] is 4, but that the multiplicative order of [4] is 2. The same computation shows that [2]-1 = [8] and [4]-1 = [4]. We can also deduce that [13] = [-2] has multiplicative order 4, that [13]-1 = [-2]-1 = [-8] = [7], and that [11]-1 = [-4]-1 = [-4] = [11]. Next, we have [7]2 = [4], so [7] has multiplicative order 4 because [7]4 = [4]2 = [1]. To compute the multiplicative order of [8], we can rewrite it as [2]3, and then it is clear that the first positive integer k with ([2]3)k = [1] is k = 4, since 3k must be a multiple of 4. (This can also be shown by rewriting [8] as [-7].) Similarly, [11] = [-4] has multiplicative order 2, and [13] = [-2] has multiplicative order 4.

```

```
6. Prove that if n > 1 is an odd integer, then (2n) = (n).

Solution: Since n is odd, the prime 2 does not occur in the prime factorization of n. The formula in Proposition 1.4.8 shows that to compute (2n) in terms of (n) we need to insert the term 2 · (1 - 1/2) in the product, and this does not change the computation.

Second solution: Since n is odd, the integers n and 2n are relatively prime, and so it follows from Exercise 1.4.27 in the text that
(2n) = (2) · (n) = (n), since (2) = 1.

```

```
7. Prove that 52n - 1 is divisible by 24, for all positive integers n.
(a) Give a proof using mathematical induction.
(b) Give a proof using congruences.

Solution: (a) Proof by induction:
For n=1, we have 52n - 1 = 24.
Next, assume that the result holds for n=k.
For n=k+1, we have the following expression.

52(k+1) - 1
= (52k)(52) - 1
= (52k)(25) - 25 + 25 - 1
= (52k - 1)(25) + 24

By the induction hypothesis, 24 is a factor of 52k - 1, and so it is follows that
24 is a factor of 52n - 1.

(b) Proof using congruences:
Since xk - 1 always has x - 1 as a factor,
(see the comment in the solution to Problem 1.2.29)
the expression 52n - 1 = (52)n - 1 always has 52 - 1 = 24 as a factor.

```

```
8. Prove that n5 - n is divisible by 30, for all integers n.

Solution: First, we can factor n5 - n as follows :
n5 - n = n(n4 - 1) = n(n-1)(n+1)(n2+1)
For any n, either n or n+1 is even.
At least one of the consecutive integers n-1, n, n+1 must be divisible by 3.
At least one of the consecutive integers n-1, n, n+1, n+2, n+3 must be divisible by 5.
If one of the first three is divisible by 5 we are done.
If 5 | n+2, then n -3 (mod 5), so n2 + 1 = (-3)2 + 1 = 10 0 (mod 5), and 5 | n2 + 1.
If 5 | n+3, then n -2 (mod 5), so n2 + 1 = (-2)2 + 1 = 5 0 (mod 5), and 5 | n2 + 1.
It follows that n5 - n must be divisible by 2, 3, and 5, so it must be divisible by 30.

```

```
Forward to §2.1 | Forward to §2.1 problems | Back to §1.4 problems | Up | Table of Contents