*Solution:*
Use the
matrix form
of the Euclidean algorithm:

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

Next problem | Next solution | Up | Table of Contents

*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}
= 1^{q} = 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.

Next problem | Next solution | Up | Table of Contents

*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).

Next problem | Next solution | Up | Table of Contents

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).

Next problem | Next solution | Up | Table of Contents

*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.

Next problem | Next solution | Up | Table of Contents

*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.

Next problem | Next solution | Up | Table of Contents

(a) Give a proof using mathematical induction.

(b) Give a proof using congruences.

*Solution:*
(a) Proof by induction:

For n=1, we have 5^{2n} - 1 = 24.

Next, assume that the result holds for n=k.

For n=k+1, we have the following expression.

5^{2(k+1)} - 1

= (5^{2k})(5^{2}) - 1

= (5^{2k})(25) - 25 + 25 - 1

= (5^{2k} - 1)(25) + 24

By the induction hypothesis,
24 is a factor of 5^{2k} - 1,
and so it is follows that

24 is a factor of 5^{2n} - 1.

(b) Proof using congruences:

Since x^{k} - 1 always has x - 1 as a factor,

(see the comment in the solution to
Problem 1.2.29)

the expression
5^{2n} - 1 = (5^{2})^{n} - 1
always has 5^{2} - 1 = 24 as a factor.

Next problem | Next solution | Up | Table of Contents

*Solution:*
First, we can factor n^{5} - n as follows :

n^{5} - n
= n(n^{4} - 1)
= n(n-1)(n+1)(n^{2}+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 n^{2} + 1 = (-3)^{2} + 1 = 10
0 (mod 5),
and 5 | n^{2} + 1.

If 5 | n+3, then
n -2 (mod 5),
so n^{2} + 1 = (-2)^{2} + 1 = 5
0 (mod 5),
and 5 | n^{2} + 1.

It follows that n^{5} - 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

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