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

Next problem | Next solution | Up | Table of Contents

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

Next problem | Next solution | Up | Table of Contents

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

Next problem | Next solution | Up | Table of Contents

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

Next problem | Next solution | Up | Table of Contents

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

Next problem | Next solution | Up | Table of Contents

*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 m^{2} - n^{2} = 8.

If m = 5 and n = 1, then m^{2} - n^{2} = 24 = 8 · 3.

If m = 5 and n = 3, then m^{2} - n^{2} = 16 = 8 · 2.

If m = 7 and n = 3, then m^{2} - n^{2} = 40 = 8 · 5.

If m = 7 and n = 5, then m^{2} - n^{2} = 24 = 8 · 3.

If m = 9 and n = 3, then m^{2} - n^{2} = 72 = 8 · 9.

If m = 9 and n = 5, then m^{2} - n^{2} = 56 = 8 · 7.

If m = 9 and n = 7, then m^{2} - n^{2} = 32 = 8 · 4.

On the other hand, if m = 2 and n = 0,
then m^{2} - n^{2} = 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
m^{2} - n^{2}, 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 m^{2} - n^{2} to get (m+n)(m-n),
so substituting for m and n we get

m^{2} - n^{2}
= (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

m^{2} - n^{2}
= (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

m^{2} - n^{2}
= (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 m^{2} - n^{2}
gives exactly what we were to prove:
if m and n are odd, then m^{2} - n^{2} is divisible by 8.

Next problem | Next solution | Up | Table of Contents

*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
n^{2} + n + 1 as n-1 plus something.
That doesn't work, but we are very close.
Dividing n^{2} + n + 1 by n-1
(using long division of polynomials)
we get a quotient of n+2 and a remainder of 3, so

n^{2} + n + 1 = (n+2)(n-1) + 3, or

3 = (n^{2} + n + 1) - (n+2)(n-1).

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

Next problem | Next solution | Up | Table of Contents

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 A^{n} = I.
We also need to show that A^{n} = I *only* when 4 | n,
and it is easier to state this as the *converse* of the first statement:
if A^{n} = 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 A^{n} = 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 A^{2}, A^{3} = A · A^{2},
A^{4} = A · A^{3}, etc.

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

A^{n} = A^{4q} = (A^{4})^{q} =
I^{q} = I.

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

A^{r} = A^{(n - 4q)} = A^{n} (A^{-4})
^{q} = I · I^{q} = I,

so r = 0 since A, A^{2}, and A^{3} are not equal to I.
We conclude that 4 | n.

Next problem | Next solution | Up | Table of Contents

*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
10^{n} + 2, for n = 1, 2, . . . ,
so we can prove the following statement:

for each positive integer n, the integer 10^{n} + 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 10^{k} + 2 is divisible by 6,
say 10^{k} + 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 10^{k+1},
to get 10^{k+1} + 2 = (10)(10^{k}) + 2,
but we need to involve the expression 10^{k} + 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.

10^{k+1} + 2
= (10)(10^{k}) + 20 - 20 + 2
= (10)(10^{k} + 2) - 18

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

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

Forward to §1.2 | Forward to §1.2 problems | Up | Table of Contents

Forward to §1.2 | Forward to §1.2 problems | Up | Table of Contents