Number Theory: In Context and Interactive

1.

Try stating and proving the division algorithm (Theorem 2.1.1) but for $b<0\text{.}$

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\text{?}$ 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\text{.}$ Calculate the gcd of some hard-looking sets of three numbers by listing divisors.

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 $gcd(a,a+2)=1$ if $a$ is odd and $gcd(a,a+2)=2$ if $a$ is even.

7.

Let $a$ be a positive integer. What is the greatest common divisor of $a$ and $a+1\text{?}$ 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.

9.

Define the least common multiple of $a$ and $b$ to be the smallest positive number which is divisible by both $a$ and $b\text{.}$ 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 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 $5\cdot {10}^n+1$ for various $n\text{.}$ Does the pattern you see continue? How would you find a counterexample, how might you prove it?

xxxxxxxxxx

@interact

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 $a,b,c\text{,}$ prove that if $a$ and $c$ are coprime, and likewise $b$ and $c$ are coprime, then $ab$ and $c$ are coprime. (Hint: use the Bezout identity.)

16.

If $gcd(a,b)=d$ and $k>0$ is an integer, prove a formula for $gcd(ka,kb)\text{.}$

17.

You probably know the Fibonacci numbers $1,1,2,3,5,8,\cdots \text{,}$ where $f_{n+2}=f_{n+1}+f_n$ and we number as $f_1=1\text{,}$ $f_2=1\text{.}$ Try applying the Euclidean algorithm to a pair of consecutive Fibonacci numbers? As a function or formula of $n\text{,}$ how long does it take? (For a more general approach see [E.2.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\text{.}$ This would start $1,1,3,5,11,21,\cdots \text{.}$

19.

Prove the second piece of Proposition 2.4.10 that if $a$ and $b$ are coprime, and if $a\mid bc\text{,}$ then $a\mid c\text{.}$ (Hint: use the Bezout identity again. Later you will have the opportunity to prove this with more powerful tools; see Exercise 6.6.6.)

20.

Find examples that contradict the conclusions of Proposition 2.4.10 if $a$ and $b$ are not coprime (i.e. share a factor greater than $1$).

21.

Verify that $gcd(a,b)=gcd(-a,-b)\text{.}$ (Contributed by Shawn Feng.)