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.

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & a & & q & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 1171 & & - & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 283 & & 4 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 39 & & 7 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 10 & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 9 & & 1 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 1 & & 9 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} }} $$

Therefore, $(1171, 283) = 1$ .


2. (a) Find the greatest common divisor of $7^2$ and $7^{50}$ .

(b) Suppose p and q are distinct prime numbers. Using the idea of (a), find the greatest commmon divisor of $p^2 q^9$ and $p^7 q^3$ .

(a) $(7^2, 7^{50}) = 7^2 = 49$ .

(b) $(p^2 q^9,\ p^7 q^3) = p^2
   q^3$ .


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 $n + 1000000$ are both divisible by 14, then so is $(n + 1000000) - n = 1000000$ . Since $14 \notdiv 1000000$ , it follows that 14 cannot divide both n and $n + 1000000$ .


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

Suppose $m + n = 171$ and $m
   - n = 130$ . Adding the two equations, I obtain $2 m = 301$ . Then $2 \mid 2 m = 301$ , 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 $k \in
   \integer$ , then $8 k + 5$ and $3 k + 2$ are relatively prime.

$$(-3)(8 k + 5) + (8)(3 k + 2) = 1.$$

Therefore, $8 k + 5$ and $3
   k + 2$ are relatively prime for all $k \in \integer$ .


6. Prove that if $n \in
   \integer$ , then $(n^2 + n + 1, n + 1) = 1$ .

$(n^2 + n + 1, n + 1) \mid n^2 +
   n + 1$ and $(n^2 + n + 1, n + 1) \mid n + 1$ , so

$$(n^2 + n + 1, n + 1) \mid (n^2 + n + 1) - n (n + 1) = 1.$$

Therefore, $(n^2 + n + 1, n + 1)
   = 1$ .


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


Contact information

Bruce Ikenaga's Home Page

Copyright 2017 by Bruce Ikenaga