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