Mathematics 243, section 1 – Algebraic Structures Solutions for Practice Exam 2 November 3, 2003

I. A) Existence: Consider the set of integers S = {a − mb : m ∈ Z}. S clearly contains positive integers. (If a > 0, then a − mb > 0 for all m ≤ 0. If a < 0, we only need to take m sufficiently negative to get a − mb > 0). Hence the set S^{+} = S ∩ Z^{+} is nonempty. By the well-ordering principle, S^{+} has a smallest element, call it s = a − mb. Note that s ≤ b since otherwise s − b = a − (m + 1)b > 0 too, and s is not the smallest positive element of S. If s = a − mb > 0, then we can take q = m and r = s to get a = qb + r satisfying the property that 0 ≤ r < b. On the other hand if s = b, then subtract one additional b from the equation a − mb = s to get a − (m + 1)b = 0, and take q = m + 1, r = 0. In either case we get q and r as claimed.

Uniqueness: We must show that if

a = q_{1}b + r_{1} a = q_{2}b + r_{2}

with 0 ≤ r_{1}, r_{2} < b, then r_{1} = r_{2} and q_{1} = q_{2}. If we subtract the two equations for a, we get

(1)  0 = (q_{1} − q_{2})b + (r_{1} − r_{2}).

Hence

(q_{1} − q_{2})b = (r_{2} − r_{1}).

This says r_{2} − r_{1} is divisible by b. But 0 ≤ r_{1}, r_{2} < b, so 0 ≤ |r_{2} − r_{1}| < b. The only integer z with 0 ≤ |z| < b that is divisible by b is z = 0. Hence r_{1} = r_{2}, and we get q_{1} = q_{2} from (1).

B) 4578 = 19 · 235 + 113: q = 19, r = 113.

II. A) We say d is a greatest common divisor of a, b if

1) d > 0,

2) d|a and d|b,

3) if c|a and c|b, then c|d.

B) Using the Euclidean algorithm we have:

\begin{aligned}488 & = 1 · 376 + 112 \\ 376 & = 3 · 112 + 40 \\ 112 & = 2 · 40 + 32 \\ 40 & = 1 · 32 + 8 \\ 32 & = 4 · 8 + 0 \end{aligned}

so the last nonzero remainder gives the gcd: gcd(488, 376) = 8. Then to find m, n with m · 488 + n · 376 = 8, set up our usual table:

k r_{k} q_{k} m_{k} n_{k}
−1 488  1  0
0 376  0  1
1 112 1 1 −1
2 40 3 −3 4
3 32 2 7 −9
4 8 1 −10 13

So (−10)(488) + (13)(376) = 8.

C) Suppose there is a solution x of the congruence ax ≡ b (mod n). Then n|(ax − b), so ax − b = qn for some n, or

(2)  b = ax − qn.

Let d = gcd(a, n). Then a = dq_{1} and n = dq_{2}. Substituting into the right side of (2), we get

b = (dq_{1})x − q(dq_{2}) = d(q_{1}x − qq_{2}).

Hence d|b.

III. The equation [17][x]+[4] = [5] in Z_{29} will have just one solution. First add −[4] = [25] to both sides, we get [17][x] = [30] = [1]. Since gcd(17, 29) = 1, [17] has a multiplicative inverse in Z_{29}, [17]^{−1} = [12] (see this by Euclidean algorithm again:

\begin{aligned}29 & = 1 · 17 + 12 \\ 17 & = 1 · 12 + 5 \\ 12 & = 2 · 5 + 2 \\ 5 & = 2 · 2 + 1 \end{aligned}

so the last nonzero remainder gives the gcd: gcd(29, 17) = 1.

k r_{k} q_{k} m_{k} n_{k}
−1 29  1 0
0 17  0 1
1 12 1 1 −1
2 5 1 −1 2
3 2 2 3 −5
4 1 2 −7 12

So (−7)(29) + (12)(17) = 1. So [17]^{−1} = [12].) The solution of our equation is [x] = [12][1] = [12].

IV. A) G corresponds to 6 and the RSA encryption function is f([x]) = [x^{e}] = [x^{1}9]. We have by repeated squaring:

6^{2} ≡ 36 (mod 143)
6^{4} ≡ 9 (mod 143)
6^{8} ≡ 81 (mod 143)
6^{16} ≡ 126 (mod 143)

Hence

6^{19} ≡ 6 · 6^{2} · 6^{16} (mod 143) ≡ 46 (mod 143)

and G encrypts to 46.

B) First we factor m = 143 = 11 · 13, so p = 11, and q = 13 are the two primes. The decryption exponent d satisfies

de ≡ 1 (mod (p − 1)(q − 1) = 120)

d = 19 is the solution of this (it’s the multiplicative inverse of [19] in Z_{120} (find using Euclidean algorithm as above). Hence 102^{19} ≡ 15 (mod 143), which corresponds to a P.