Try the Free Math Solver or Scroll down to Tutorials!

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


Number Theory Homework 4 Solution

1. Given three integers a, b, c with c > 0, prove that lcm(ac, bc) = c ยท lcm(a, b).
Solution:

2. Use the Euclidean algorithm to compute lcm(357,−629, 221).
Solution: Since lcm(357,−629, 221) = lcm(lcm(357,−629), 221), we’ll first compute
lcm(357,−629) = lcm(357, 629). Using the Euclidean algorithm,

So gcd(357, 629) = 17, and thus lcm(357, 629) = = 13209. Next, we calculate
lcm(13209, 221). Again, using the Euclidean algoirthm,

Therefore, gcd(13209, 221) = 17, and hence lcm(13209, 221) = = 171717

3. For any integer n, show that lcm(9n + 8, 6n + 5) = 54n^2 + 93n + 40.
Solution: For any integer n, we can write 1 = 2(9n + 8) − 3(6n + 5). This tells us
gcd(9n + 8, 6n + 5) = 1. So

4. (a) Use the Fundamental Theorem of Arithmetic to prove that gcd(an, bn) = (gcd(a, b))n for
any positive integer n. If particular, if a and b are relatively prime, then so are an and
bn.

Proof. By TFA, we can write where are distinct
primes and . Let for all i. Then , and
so

On the other hand,
Note that for each i, = = Therefore,

(b) If divides , must a divide b? Explain your answer.
Solution: Yes. If , then From part (a), we know =
. Combining, we get gcd(a, b) = a, and therefore a|b.

5. Without using the Euclidean algorithm, find the greatest common divisor and least common
multiple of a = and b =. You may leave your answer
in factored form.

Solution: gcd(a, b) = and lcm(a, b) =

6. Without quoting Dirichlet’s Theorem, prove that there are infinitely many primes of the form
6k − 1.

Proof. First note that by the division algorithm, every odd prime greater than 3 is of the
form 6k + 1 or 6k + 5. Since 6k + 5 = 6(k + 1) − 1, it is true that every odd prime is of the
form 6k + 1 or 6k − 1.

Now suppose that there are finitely many primes of the form 6k−1, say Consider
the number N = − 1. Since N is of the form 6k − 1 and for all i, N is an
odd composite integer and so must have prime factors of the form 6k + 1 or 6k − 1.

Note that the product of two numbers of the form 6k + 1 is again of that form. Thus, N
has a prime divisor of the form 6k −1, i.e. for some j. But this means , impossible.
Hence, there are infinitely many primes of the form 6k − 1.