Try the Free Math Solver or Scroll down to Tutorials!

 Depdendent Variable

 Number of equations to solve: 23456789
 Equ. #1:
 Equ. #2:

 Equ. #3:

 Equ. #4:

 Equ. #5:

 Equ. #6:

 Equ. #7:

 Equ. #8:

 Equ. #9:

 Solve for:

 Dependent Variable

 Number of inequalities to solve: 23456789
 Ineq. #1:
 Ineq. #2:

 Ineq. #3:

 Ineq. #4:

 Ineq. #5:

 Ineq. #6:

 Ineq. #7:

 Ineq. #8:

 Ineq. #9:

 Solve for:

 Please use this form if you would like to have this math solver on your website, free of charge. Name: Email: Your Website: Msg:

# 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.