MATH 110 Introduction to Number Theory Winter 2023 Homework 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Homework 2 (due Jan. 29)
MATH 110 | Introduction to Number Theory | Winter 2023
Whenever you use a result or claim a statement, provide a justification or a proof, unless it has been covered in the class. In the later case, provide a cita- tion (such as“by the 2- out- of-3 principle”or“by Coro. 0.31 in the textbook”).
You are encouraged to discuss the problems with your peers. However, you must write the homework by yourself using your words and acknowledge your collaborators.
Problem 1. Let a, b and n be positive integers. Prove that
(a) (5 pts) gcd(an ,bn ) = gcd(a,b)n and lcm(an ,bn ) = lcm(a,b)n;
(b) (5 pts) gcd(a · n,b · n) = gcd(a,b) · n and lcm(a · n,b · n) = lcm(a,b) · n;
Problem 2 (10 pts). Write the prime factorization of N = 13! and then count the divisors of N (give the number, you do not need to list all of them in order to count).
Remark. Recall that for any positive integer n, we denote by n! (read n factorial) the product of all the integers between 1 and n.
Problem 3 (10 pts). Let n be any positive integer. Prove that there exists a positive integer k (depending on n) such that the following list of n consecutive integers:
k,k + 1, ··· ,k + n − 1
contains no prime number at all.
Hint. Use the factorial (but k = n! is NOT the correct answer, start from this and try to see what are missing). You also need the 2- out- of-3 property of division.
Remark. From the problem, we can see that the gaps between consecutive prime numbers can be arbitrarily large.
Problem 4. As in class, consider the collection of complex numbers of the form
O :={a + b^−5 I a,b ∈ Z}.
(a) (3 pts) Prove that the set O equipped with the addition and multiplication of complex numbers satisfies the following properties:
(i) O is closed under addition: for any α,β ∈ O, we have α + β ∈ O. (ii) O is closed under negation: for any α ∈ O, we have −α ∈ O. (iii) O is closed under multiplication: for any α,β ∈ O, we have αβ ∈ O.
Remark. In the terms of Algebra, O is a subring of the ring C of complex numbers.
(b) (4 pts) Consider the integer-valued function N defined on O:
N(a + b√−5) := a2 + 5b2 .
Prove that
N(αβ) = N(α)N(β)
for any two elements α and β in O.
Remark. Say that an element α ∈ O divides another element β ∈ O, denoted by α | β if there is an element γ ∈ O such that β = αγ . Hence, problem 4.(b) shows that
α | β =⇒ N(α) | N(β).
(c) (2 pts) Say that an element ε ∈ O is a unit if ε divides 1. Prove that all the units in O are 1 and −1.
Hint. Assume ε ∈ O is a unit other than ±1, then use problem 4.(b).
(d) (8 pts) Say that an element α ∈ O is a prime element if
(i) α is nonzero and not a unit;
(ii) whenever α = γδ with γ,δ ∈ O, we necessarily have one of γ,δ being a unit. Prove that the following four elements are prime elements: 2, 3, 1+ √−5, and 1 − √−5. Hint. Proceed by way of contradiction, then use problem 4.(b).
(e) (3 pts) Say that two elements α,β ∈ O are associated if both α | β and β | α . Prove that none pair of the four elements 2, 3, 1 + √−5, and 1 − √−5 are associated. Hint. Use the definition of division and problem 4.(c).
Remark. A prime factorization of a nonzero element α ∈ O is a representation
α = εp1 ··· pn ,
where ε ∈ O is a unit and p1 , ··· ,pn ∈ O are prime elements in O. Say that α has a unique
prime factorization if whenever there is another prime factorization
α = ε\p
··· p
,
we necessarily have m = n and there is a bijection ϕ : {1, ··· ,n} → {1, ··· ,m} such that each pi (1 ⩽ i ⩽ n) is associated to p
(i) .
Say that the unique prime factorization property holds in O if any nonzero element α ∈ O has a unique prime factorization.
Then problem 4 shows that the prime factorization property fails in O due to the following counterexample
6 = 2 · 3 = (1 + √−5) · (1 − √−5).
2023-02-13