## § 1.1 Divisors: Solved problems

22. Find gcd (435, 377), and express it as a linear combination of 435 and 377.

Comment: You definitely need to know how to do these computations.

Solution: We will use the Euclidean algorithm. Divide the larger number by the smaller, which gives you a quotient of 1 and a remainder of 58. Then divide the remainder 58 into 377, and continue the Euclidean algorithm. (See Example 1.1.4 in the text if you need more help.) You should get the following equations.

435 = 1 · 377 + 58

377 = 6 · 58 + 29

58 = 2 · 29

Thus gcd (435,377) = gcd (377,58) = gcd (58,29), and the repeated divisions show that gcd (435, 377) = 29, since the remainder in the last equation is 0.

To write 29 as a linear combination of 435 and 377 we need to use the same equations, but we need to solve them for the remainders.

58 = 435 - 1 · 377

29 = 377 - 6 · 58

Now take the equation involving the remainder 29, and substitute for 58, the remainder in the previous equation.

29 = 377 - 6 · 58

= 377 - 6 · (435 - 1 · 377)

= 7 · 377 - 6 · 435

This gives the linear combination we need, 29 = (7)(377) + (-6)(435).

```

```
23. Find gcd (3553, 527), and express it as a linear combination of 3553 and 527.

Comment: This time we will use the matrix form of the Euclidean algorithm. You should be able to use both the back-solving form (as in Problem 1.1.22,) and the matrix form. In Chapter 4, the Euclidean algorithm is used for polynomials, and the matrix method just gets too complicated, so we have to adapt the back-solving method.

Solution: Just as in Problem 1.1.22, the first step is to divide the smaller number into the larger. We get

3553 = 6 · 527 + 391,

so this tells us to multiply the bottom row of the matrix by 6 and subtract from the first row. The steps in the Euclidean algorithm produce the following equations.

3553 = 6 · 527 + 391,

527 = 1 · 391 + 136,

391 = 2 · 136 + 119

136 = 1 · 119 + 17

119 = 7 · 17

Using these equations as a guide, the rest of the steps in reducing the matrix to the form we want should be clear.

Therefore gcd (3553, 527) = 17, and 17 = (-4) (3553) + (27) (527).

Comment: The first row of the final matrix shows that
0 = (31) (3553) + (-209) (527), so we could add any multiple of this equation to
17 = (-4) (3553) + (27) (527) and still have a linear combination of 3553 and 527 equal to 17. Thus the given answer is not unique.

```

```
24. Which of the integers 0, 1, . . . , 10 can be expressed in the form 12m + 20n, where m,n are integers?

Solution: Theorem 1.1.6 provides the answer. An integer k is a linear combination of 12 and 20 if and only if it is a multiple of their greatest common divisor, (gcd) which is 4. Therefore we can express 0, 4, and 8 in the required form, but we can't do it for the rest.

Comment: Check out the answer in concrete terms. We can write

0 = 12 · 0 + 20 · 0;

4 = 12 · 2 + 20 · (-1);

8 = 12 · (-1) + 20 · 1.

```

```
25. If n is a positive integer, find the possible values of gcd (n, n+10).

Solution: Let d = gcd (n, n+10). Then d | n and d | (n+10), so we must have d | 10, and therefore d is limited to one of 1, 2, 5, or 10. Can each of these occur for some n?
Yes: gcd(3,13) = 1;     gcd(2,12) = 2;     gcd(5,15) = 5;     gcd(10,20) = 10.

```

```
26. Prove that if a and b are nonzero integers for which a | b and b | a, then b = ± a.

Comment: The first step is to use Definition 1.1.1, to rewrite a | b and b | a as equations, to give something concrete to work with.

Solution: Since a | b, there is an integer m with b = ma. Since b | a, there is an integer k with a = kb. Substituting a = kb in the equation b = ma we get b = m(kb), so since b is nonzero we can cancel it to get 1 = mk. Since both m and k are integers, and |1| = |m| · |k|, we must have |m| = 1 and |k| = 1, so either b = a or b = - a.

```

```
27. Prove that if m and n are odd integers, then m2 - n2 is divisible by 8.

Comment: You might want to check this out for a few small values of m and n, just to get a feel for the problem, and to see if you really believe it.

If m = 3 and n = 1, then m2 - n2 = 8.
If m = 5 and n = 1, then m2 - n2 = 24 = 8 · 3.
If m = 5 and n = 3, then m2 - n2 = 16 = 8 · 2.
If m = 7 and n = 3, then m2 - n2 = 40 = 8 · 5.
If m = 7 and n = 5, then m2 - n2 = 24 = 8 · 3.
If m = 9 and n = 3, then m2 - n2 = 72 = 8 · 9.
If m = 9 and n = 5, then m2 - n2 = 56 = 8 · 7.
If m = 9 and n = 7, then m2 - n2 = 32 = 8 · 4.

On the other hand, if m = 2 and n = 0, then m2 - n2 = 4. This one counterexample shows that the result is not true for all possible cases of m and n, so there must be some restrictions on m and n.

The experimental answers, for 8 of the infinitely many pairs of odd integers, don't prove anything. They don't even seem to hint at a possible approach to the problem. Perhaps we could say one thing: in the general case, we could try to find a general expression for m2 - n2, and then try to factor out the integer 8.

Solution: First, we need to use the given information about m and n. Since they are odd, we can write them in the form m = 2k + 1 and n = 2q + 1, for some integers k and q. We can factor m2 - n2 to get (m+n)(m-n), so substituting for m and n we get

m2 - n2 = (2k+1+2q+1)(2k+1-2q-1) = (2)(k+q+1)(2)(k-q) .

Now we need to take two cases.

If k-q is even, then k-q has 2 as a factor. We can suppose that k-q = 2p, for some integer p. In this case, substituting for k-q gives us

m2 - n2 = (2)(k+q+1)(2)(k-q) = (2) (k+q+1) (2) (2) (p) = (8) (k+q+1) (p) .

If k-q is odd, then k+q=(k-q)+(2q) is the sum of an odd integer and an even integer, so it must also be odd. That means that k+q+1 is even, so it has 2 as a factor. Now we can suppose that k+q+1 = 2t, for some integer t. In this case, substituting for k+q+1 gives us

m2 - n2 = (2)(k+q+1)(2)(k-q) = (2) (2) (t) (2) (k-q) = (8) (k-q) (t) .

Showing that we can factor 8 out of m2 - n2 gives exactly what we were to prove: if m and n are odd, then m2 - n2 is divisible by 8.

```

```
28. Prove that if n is an integer with n > 1, then gcd (n-1, n2+n+1) = 1 or gcd (n-1, n2+n+1) = 3.

Comment: As in the previous problem, it's not a bad idea to check this out for some values of n, just to bet a bit of any idea of what is going on.
For n=3, we have gcd (2,13) = 1.
For n=4, we have gcd (3,21) = 3.
For n=5, we have gcd (4,31) = 1.
For n=6, we have gcd (5,43) = 1.
For n=7, we have gcd (6,57) = 1.
These calculations don't prove anything, but maybe they do make the problem look plausible.

Solution: Problem 1.1.25 gives a hint. In that problem, since the gcd was a divisor of n and n+10, it had to be a divisor of 10. To use the same approach, we would have to write n2 + n + 1 as n-1 plus something. That doesn't work, but we are very close. Dividing n2 + n + 1 by n-1 (using long division of polynomials) we get a quotient of n+2 and a remainder of 3, so

n2 + n + 1 = (n+2)(n-1) + 3, or

3 = (n2 + n + 1) - (n+2)(n-1).

Now we can see that any common divisor of n-1 and n2 + n + 1 must be a divisor of 3, so the answer has to be 1 or 3.

```

```
29. Prove that if n is a positive integer, then

if and only if 4 | n.

Comment: Let's use A for the matrix, and I for the identity matrix. The proof must be given in two pieces. We need to show that if 4 | n, then An = I. We also need to show that An = I only when 4 | n, and it is easier to state this as the converse of the first statement: if An = I, then 4 | n. The first half of the proof is easier than the second, since it just takes a computation. In the second half of the proof, if An = I then we will use the division algorithm, to divide n by 4, and then show that the remainder has to be 0.

Solution: We begin by computing A2, A3 = A · A2, A4 = A · A3, etc.

Now we can see that if 4 | n, say n = 4q, then

An = A4q = (A4)q = Iq = I.

Conversely, if An = I, we can use the division algorithm to write n = 4q + r, with 0 r < 4. Then

Ar = A(n - 4q) = An (A-4) q = I · Iq = I,

so r = 0 since A, A2, and A3 are not equal to I. We conclude that 4 | n.

```

```
30. Give a proof by induction to show that each number in the sequence 12, 102, 1002, 10002, . . . , is divisible by 6.

Comment: If you are unsure about doing a proof by induction, you should read Appendix 4 in the text.

Solution: To give a proof by induction, we need a statement that depends on an integer n. We can write the numbers in the given sequence in the form 10n + 2, for n = 1, 2, . . . , so we can prove the following statement:

for each positive integer n, the integer 10n + 2 is divisible by 6.

The first step is to check that the statement is true for n = 1. (This ``anchors'' the induction argument.) Clearly 12 is divisible by 6.

The next step is to prove that if we assume that the statement is true for n = k, then we can show that the statement must also be true for n = k+1. Let's start by assuming that 10k + 2 is divisible by 6, say 10k + 2 = 6q, for some q in Z, and then look at the expression when n = k+1. We can easily factor a 10 out of 10k+1, to get 10k+1 + 2 = (10)(10k) + 2, but we need to involve the expression 10k + 2 in some way. Adding and subtracting 20 makes it possible to get this term, and then it turns out that we can factor out 6.

10k+1 + 2 = (10)(10k) + 20 - 20 + 2 = (10)(10k + 2) - 18

= (10)(6q) - (6)(3) = (6)(10q - 3)

We have now shown that if 10k + 2 is divisible by 6, then 10k+1 + 2 is divisible by 6. This completes the induction.

```

```