1

Try stating and proving the division algorithm (Theorem 2.1.1) but for \(b\lt 0\).

2

Can you find an \(n\) such that the possible remainders of a perfect square when divided by \(n\) are all numbers between zero and \(n-1\)? If you can, how many different such \(n\) can you find? If not, can you prove there are none?

3

Write the gcd of 3 and 4 as a linear combination of 3 and 4 in three different ways. (Hint: trial and error.)

4

You can define the gcd of more than two numbers as the greatest integer dividing all of the numbers in your set. So, for instance, \(\gcd(20,30,70)=10\). Calculate the gcd of some hard-looking sets of three numbers by listing divisors.

Sage allows you to calculate arbitrary gcds like this.

5

Find the gcd of the four numbers 1240, 6660, 15540, and 19980 without Sage.

6

Prove that \(\gcd(a,a+2)=1\) if \(a\) is odd and \(\gcd(a,a+2)=2\) is \(a\) is even.

7

Let \(a\) be a positive integer. What is the greatest common divisor of \(a\) and \(a+1\)? Prove it.

8

Use the Euclidean algorithm to find the gcd of 51 and 87, and then to write that gcd as a linear combination of 51 and 87. Do the same thing for 151 and 187. Find another way to write the gcd of one of these pairs as a linear combination.

9

Define the least common multiple of \(a\) and \(b\) to be the smallest positive number which is divisible by both \(a\) and \(b\). Prove that the least common multiple of \(a\) and \(b\) is \(ab\) precisely when \(a\) and \(b\) are coprime.

10

Find the gcd of 151 and 187 using the Euclidean algorithm, then write it as a linear combination of these two numbers in two different ways.

11

Find the gcd of 500000001 and 5000001 in any way you see fit other than asking someone else.

12

Does the pattern you see in the following interact continue? How would you find a counterexample, how might you prove it?

13

Find the gcd of three four digit numbers, none of which is divisible by ten.

14

To make the proof of the Euclidean algorithm, Algorithm 2.3.2, very complete, one would want to use induction to replace “and so forth” verbiage. Do so for practice with induction.

15

Prove that if \(a\) and \(c\) are coprime, and likewise \(b\) and \(c\) are coprime, then \(ab\) and \(c\) are coprime. (Hint: use Bezout.)

16

If \(\gcd(a,b)=d\) and \(k>0\), prove a formula for \(\gcd(ka,kb)\).

17

You probably know the Fibonacci numbers \(1,1,2,3,5,8,\cdots\), where \(f_{n+2}=f_{n+1}+f_{n}\) and we number as \(f_1=1\), \(f_2=1\). Try applying the Euclidean algorithm to a pair of consecutive Fibonacci numbers? How long does it take compared to \(n\)? (For a more general approach see [C.1.1, Exercises 1.17-1.19].)

18

Try the above exercise again, but with a variant of the Fibonacci numbers where \(f_{n+2}=f_{n+1}+2f_{n}\). This would start \(1,1,3,5,11,21,\cdots\).

19

Prove that if \(a\) and \(b\) are coprime, and if \(a\mid bc\), then \(a\mid c\). (Hint: use the Bezout fact again.)

20

Find examples that contradict the facts about coprime integers (Proposition 2.4.6) if \(a\) and \(b\) do share a factor greater than \(1\).

21

We discussed relatively prime numbers in this chapter. Write down your own definition of a prime number. Then compare it with the book, a few internet sources, or some other authoritative source. Should 1 be considered prime? What about \(-1\)?

22

Search books and/or the Internet and find at least three different proofs that there is no largest prime number. (Ours, Theorem 6.2.1, is the oldest one we know of.) You don't have to understand all the details; they should be fairly different from each other, though. Do any of the proofs generate all primes in order?