# Solutions to Problem Set 21

Math 310-01/02

11-8-2017

1. Find the greatest common divisor of 1171 and 283 without factoring the numbers.

Therefore, .

2. (a) Find the greatest common divisor of and .

(b) Suppose p and q are distinct prime numbers. Using the idea of (a), find the greatest commmon divisor of and .

(a) .

(b) .

3. Calvin Butterball takes an integer n and adds 1000000 to get another integer. Can both of the integers be divisible by 14? Why or why not?

If n and are both divisible by 14, then so is . Since , it follows that 14 cannot divide both n and .

4. Prove that it is not possible to find two integers m and n whose sum is 171 and whose difference is 130.

Suppose and . Adding the two equations, I obtain . Then , which is a contradiction. Thereore, it is not possible to find two integers m and n whose sum is 171 and whose difference is 130.

5. Prove that if , then and are relatively prime.

Therefore, and are relatively prime for all .

6. Prove that if , then .

and , so

Therefore, .

No person is a friend who demands your silence, or denies your right to grow. - Alice Walker

Contact information