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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8002237,"math_prob":0.9984787,"size":2188,"snap":"2021-43-2021-49","text_gpt3_token_len":762,"char_repetition_ratio":0.12362637,"word_repetition_ratio":0.09213483,"special_character_ratio":0.37111518,"punctuation_ratio":0.18903592,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998714,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66],"im_url_duplicate_count":[null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-17T01:22:49Z\",\"WARC-Record-ID\":\"<urn:uuid:7479a116-bf51-45f6-92d7-38ef47a10353>\",\"Content-Length\":\"85669\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:953801ad-01d2-4744-8d4d-f4ef6c1754c9>\",\"WARC-Concurrent-To\":\"<urn:uuid:e0a5c887-ec2c-4a36-9a06-cf02743a0df3>\",\"WARC-IP-Address\":\"54.197.228.212\",\"WARC-Target-URI\":\"https://alegremath.com/number-theory-homework-4-solution.html\",\"WARC-Payload-Digest\":\"sha1:2FJ3R4F4FLXCM7AFODPLTWG7WLFXXLO4\",\"WARC-Block-Digest\":\"sha1:ZUX65WWOMTAJLZJS4WQJ32XNIFJISPWE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585045.2_warc_CC-MAIN-20211016231019-20211017021019-00514.warc.gz\"}"}