Number theory proofs problem set Academic Essay

Number theory proofs problem set

Problem 1
(a) Prove or Disprove: For all ?, ?, ? ∈ ℤ
+, if ?|??, then ?|? or ?|?.
Note! ℤ
+ is the set of all positive integers.
(b) Prove or Disprove: For all ?, ? ∈ ℤ≥2 where ?|?, if ?≡? (mod ?) (where ?, ? ∈ ℤ), then
?≡? (mod ?). Note! ℤ is the set of all integers. ℤ≥2 is the set of all integers ≥ 2.
Problem 2
(a) Prove or Disprove: For all integers ? ∈ ℤ
∗
, ?
2 + ? + 41 is a prime number.
Note! ℤ
∗
is the set of all positive integers including 0.
(b) Prove or Disprove: 2 is the only even prime number.
Problem 3
(a) Prove or Disprove: For all ? ∈ ℤ
+, ? and ? + 1 are relatively prime.
(b) Prove or Disprove: For all ? ∈ ℤ
+, ? and ? + 2 are relatively prime.
(c) Prove or Disprove: For all ? ∈ ℤ
+, if ? is odd, then ? and ? + 2 are relatively prime.
(d) Prove or Disprove: For all ?, ?, ? ∈ ℤ≥2 if ?|? and ?|?, then ? + ? and ? are not relatively
prime.
Note! ℤ
+ is the set of all positive integers. ℤ≥2 is the set of all integers ≥ 2.
Problem 4 Least Common Multiple (lcm)
Say we have the integer ? = 204,459,408,000, and suppose we know that ? = lcm(a, b) and
? = 709,928,500. How many possible values of ? are there if ? is a positive integer?
(Hint: All of ? and ?’s prime factors are ≤ 29.)
Problem 5 Greatest Common Divisor (gcd)
Use the Extended Euclidean Algorithm to express gcd (225, 431) as a linear combination of 225
and 431.
(Hint: There’s a great YouTube video that can help with this if you search “Extended Euclidean
Algorithm”)
Problem 6
Consider a discrete random variable, ?, with the following probability distribution:
What is the expected value of ??