Exercises 2.5 Exercises
1.
Try stating and proving the division algorithm (Theorem 2.1.1) but for
2.
Can you find an
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,
With Sage you can calculate arbitrary gcds like this, so you can check your work in this problem using the same command as before, but with slightly different syntax.
xxxxxxxxxx
gcd([3800,7600,1900])
5.
Find the gcd of the four numbers 1240, 6660, 15540, and 19980 without Sage.
6.
Prove that
7.
Let
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.
9.
Define the least common multiple of
10.
Find the gcd of 151 and 187 using the Euclidean algorithm, then write the gcd 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.
In the following interact you can explore the gcd of numbers of the form
xxxxxxxxxx
def _(m=(3,[1..20]),n=(2,[1..20])):
pretty_print(html("The gcd of ${}$ and ${}$ is ${}$".format(5*10^m+1, 5*10^n+1, gcd(5*10^m+1,5*10^n+1))))
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.3, very complete, one would want to use induction to replace βand so forthβ verbiage. Do so for practice with induction.
15.
For nonzero
16.
If
17.
You probably know the Fibonacci numbers
18.
Try the above exercise again, but with a variant of the Fibonacci numbers where
19.
Prove the second piece of Proposition 2.4.10 that if
20.
Find examples that contradict the conclusions of Proposition 2.4.10 if
21.
Verify that
The next two exercises consider a related concept to relatively prime.
22.
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
23.
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?