Full question is attached below with sample paper…. Nochatgpt and plagiarism please. Work should be 100% accurate
11.
Math 3053 Homework 1
Sample Answers
Point Breakdown
Definitions
1. Recall that an integer a divides an integer b provided there exists an integer c such that
b = a · c.
(a) Give two examples of integers a and b where a divides b but b does not divide a.
a = 2, b = 4 and a = 3, b = 6
(b) Does the integer 0 divide the integer 0? Explain.
Yes, using the definition above, 0 = 0 · c for any integer c, so 0 does divide 0.
(c) If a is any nonzero integer, does 0 divide a? Explain.
If 0 divides a, then there must exist some integer c such that a = 0 · c, but this is not
possible since any number times 0 is 0.
2. What is the difference between first and second principle mathematical induction?
After the base case, first principle induction assumes that the result holds for n and proves
the result holds for n + 1. Second principle induction assumes that the result holds for all
k ≤ n and proves the result holds for n + 1.
Important Results
3. If two integers a and b are relatively prime, state two facts we know about them.
i. They have no common factors, i.e., gcd(a, b) = 1.
ii. There exist integers s and t such that 1 = a · s + b · t.
4. In your own words, describe the following types of proofs:
(a) Direct proof
Put the assumptions together to get the conclusion.
(b) Proof by contradiction
Assume the assumptions are true and the conclusion is false to get a contradiction.
(c) Proof by induction
Show the result holds for the smallest possible number. Then assume it holds for some
value n and prove it also holds for n + 1.
5. State the Fundamental Theorem of Arithmetic in your own words.
Every integer is either a prime or a product of primes.
Applications of Definitions and Results
6. Find two pairs of integers s and t such that 1 = 5 · s + 7 · t.
s = 10, t = −7 and s = 3, t = −2
7. For every positive integer n, prove that
1 + 3 + 5 + · · · + (2n − 1) = n2 .
Base Case: If n = 1, then 1 = 12 .
Assume that 1 + 3 + 5 + · · · + (2n − 1) = n2 . Then
1 + 3 + 5 + · · · + (2n − 1) + (2n + 1) = n2 + (2n + 1)
1 + 3 + 5 + · · · + (2n − 1) + (2n + 1) = n2 + 2n + 1
1 + 3 + 5 + · · · + (2n − 1) + (2n + 1) = (n + 1)(n + 1)
1 + 3 + 5 + · · · + (2n − 1) + (2n + 1) = (n + 1)2
Therefore, the result holds for n + 1 and we are done.
8. For a, b ∈ Z, define a ∼ b if a + b is even. Prove that ∼ is an equivalence relation on Z and
describe its equivalence classes.
i. Reflexivity: a + a = 2a is even. ✓
ii. Symmetry: If a + b is even then b + a is even since a + b = b + a. ✓
iii. Transitivity: Assume a ∼ b and b ∼ c. Therefore a + b is even and b + c is even. Then
(a + b) + (b + c) = a + 2b + c is even and a + c = (a + b) + (b + c) − 2b is also even.
Therefore a ∼ c. ✓
Connections
9. Euler’s totient function is an important function in number theory and crypotgraphy. For a
given integer n, the function counts the positive integers up to n that are relatively prime to
n. For example, ϕ(4) = 2, since of the integers 1, 2, and 3, only 1 and 3 are relatively prime
to 4.
(a) Calculate ϕ(6), ϕ(8), and ϕ(12).
ϕ(6) = 2 since 6 is relatively prime with 1 and 5.
ϕ(8) = 4 since 8 is relatively prime with 1, 3, 5, and 7.
ϕ(12) = 4 since 12 is relatively prime with 1, 5, 7, and 11.
(b) What can you say about ϕ(n) when n is prime?
When n is prime, it is relatively prime with all other integers, so ϕ(n) = n − 1.
10. One important result in number theory is the fact that there are infinitely many prime numbers. A proof by contradiction of this result is: Assume there are finitely many prime numbers p1 , p2 , . . . , pn . Set P to be the product of these primes as P = p1 · p2 · · · · pn . Set
N = P + 1 = p1 · p2 · · · · pn + 1. By the Fundamental Theorem of Arithmetic, either N is a
new prime or it is a product of primes. Notice that N is not divisible by any of the primes
p1 , p2 , . . . , pn since it would have a remainder of 1 when divided by any of them. Therefore
N is not a product of existing primes, so it must be a new one. Therefore if we assume there
are finitely many primes, we can construct a new one, so there must be infinitely many.
Page 2 of 2
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
