xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

数学代写-MATH10101

时间：2021-01-23

MATH10101 Foundations of Pure Mathematics A

Mock assessment

1. (i) Write down the negation of the statement

∀n ∈ Z, if 3n+ 2 is odd , then n is odd .

Prove that the statement is true.

(ii) Use mathematical induction to prove that for all n ∈ N, 3 divides

4n + 2.

(10 marks)

2. (i) Let A,B,C and D be sets. Prove that

(A\C)× (B\D) ⊆ (A×B)\(C ×D).

Give an example where (A\C)× (B\D) 6= (A×B)\(C ×D).

(In this question you may assume that if S = ∅ or T = ∅, then

S × T = ∅.)

(ii) Let A be a denumerable set and f : R → A be a function. Prove

that f is not injective.

(10 marks)

3. (i) Let f : N → N be defined by f(n) = n2 − n + 1. Show that f is

injective. Is f surjective? Explain your answer.

(ii) Explain why the set of even integers and the set {k2 : k ∈ Z} are

equipotent. (You may state without proof any results from the lecture

notes.)

(10 marks)

4. (i) Let R be a relation defined on a set X. We define Rc to be the

relation where

xRcy ⇐⇒ (x, y) /∈ R.

Prove that R is symmetric =⇒ Rc is symmetric.

(ii) If R is an equivalence relation, must Rc be an equivalence relation?

Give a proof or counterexample. If you give a counterexample, also

determine whether Rc is reflexive, symmetric, or transitive for your

counterexample.

(10 marks)

5. (i) Let p be a prime. Prove that if x2 ≡ 1 mod p then either x ≡ 1

mod p or x ≡ −1 mod p. You may use results from the course

provided they are explicitly stated.

(ii) Let p be a prime. How many congruence classes [x]p are there such

that [x2]p = [1]p?

(iii) Let m ≥ 2 be an integer. If x2 ≡ 1 mod m must x ≡ ±1 mod m?

Give a proof or counterexample.

(10 marks)

6. (i) Find all solutions x ∈ Z to the linear congruence

7x ≡ 21 mod 42,

by reducing the problem to a linear Diophantine equation in two un-

knowns. You may use results from the course provided they are ex-

plicitly stated.

(ii) Find a multiplicative inverse for 5 modulo 42, you do not need to

explain your method.

(iii) Hence or otherwise find all x ∈ Z such that

5x ≡ 21 mod 42.

(10 marks)

7. (i) Let n ≥ 2 be an integer. Show that

φ(n2)

n

= φ(n),

where φ is Euler’s phi-function. You may use results from the course

provided they are explicitly stated, including the formula for φ(n).

(ii) Is there an integer n with φ(n) = 11? Justify your answer.

(10 marks)

8. (i) Use Fermat’s Little Theorem or Euler’s Theorem to calculate the

remainder of 1012 on division by 7.

(ii) Calculate the remainder of 1012 on division by 28, showing your work-

ing.

(10 marks)

Solutions

1. (i) The negation is ∃n ∈ Z, 3n+ 2 is odd and n is even. (1 mark)

We prove the original statement using proof by contradiction. Assume

the negation is true. Since n is even we can write n = 2k for some

k ∈ Z. Then 3n+2 = 6k+2 = 2(3k+1) is even because 3k+1 ∈ Z.

This contradicts our assumption that 3n + 2 is odd. Therefore the

statement is true. (4 marks)

(ii) Let P (n) be the statement 3 divides 4n + 2.

Base case: P (1) is true because 3 divides 41 + 2 = 6.

Inductive step: Let k ∈ N and assume P (k) is true, ie. 3 divides

4k + 2. Then 4k + 2 = 3m for some m ∈ Z. We have 4k+1 + 2 =

4.4k + 2 = 4(3m − 2) + 2 = 3(4m − 2) and this is divisible by 3

because 4m− 2 ∈ Z. Therefore P (k + 1) is true.

By induction, P (n) is true for all n ∈ N. (5 marks)

2. (i) Let (x, y) ∈ (A\C) × (B\D). Then x ∈ A\C and y ∈ B\D.

Therefore (x, y) ∈ A × B and (x, y) /∈ C × D. Hence (x, y) ∈

(A×B)\(C ×D) and (A\C)× (B\D) ⊆ (A×B)\(C ×D).

(5 marks)

If A = {1, 2}, B = {3, 4}, C = {1}, D = {3} we have

(A\C)×(B\D) = {(2, 4)},(A×B)\(C×D) = {(1, 4), (2, 3), (2, 4)}.

(1 mark)

(ii) Let A be a denumerable set and f : R → A be a function. Assume

that f is injective. Let g : R → Imf be defined by g(x) = f(x)

for all x ∈ R. Then g is surjective and injective and so g is a

bijection. Therefore R is equipotent with the image of f . Since

A is denumerable Imf is countable. his contradicts the fact that R

is uncountable. Therefore f is not injective. (4 marks)

3. (i) Assume n,m ∈ N. We have

f(n) = f(m)

⇒ n2 − n+ 1 = m2 −m+ 1

⇒ n2 −m2 = n−m

⇒ (n−m)(n+m) = n−m.

Therefore n = m or n + m = 1. Since n,m ∈ N we can’t have

n+m = 1. Hence n = m and f is injective. (4 marks)

We can see that f is not surjective because f(1) = 1, f(2) = 3 and

f(n) > n2 + 1 > 4 for all n > 2. Therefore 2 is not in the image of

f . (2 marks)

(ii) To show the sets are equipotent we need to find a bijection between

them. Let A = {2k : k ∈ Z} and B = {k2 : k ∈ Z}. A and B are

infinite subsets of the denumerable set Z and therefore they are both

denumerable. Hence there exist bijections f : N→ A and g : N→ B.

The inverse of f is also a bijection. The map g ◦ f−1 : A → B is

the composite of two bijections and therefore it is a bijection. By

definition A and B are equipotent. (4 marks)

4. (i) We need to show xRcy =⇒ yRcx. So assuming xRcy we have

(x, y) /∈ R by definition. SinceR is symmetric we must have (y, x) /∈

R. Then by definition we have yRcx, as required. (5 marks)

(ii) A counterexample is when R is the equivalence relation = on Z.

Then Rc is precisely the relation 6=. Now 1 = 1 and so we do not

have 1 6= 1, so 6= is not reflexive. We have already shown that 6= is

symmetric because = is. Finally, 6= is not transitive because 1 6= 2,

2 6= 1, but it is not the case that 1 6= 1. (5 marks)

5. (i) We observe x2 − 1 ≡ 0 mod p and therefore p divides x2 − 1 =

(x− 1)(x+1). Euclid’s property of primes states that if p divides ab

then either p divides a or p divides b. Therefore p divides (x− 1) or

p divides (x+1). Therefore x− 1 ≡ 0 mod p or x+1 ≡ 0 mod p.

Rearranging these congruences, we obtain the result required. (5

marks)

(ii) If p = 2 then there is only one congruence class namely [1]2. If p ≥ 3

is prime then there are two congruence classes [1]p and [−1]p by the

previous part. (2 marks)

(iii) A counterexample is m = 8 and x = 3, we observe that x2 = 9 ≡ 1

mod 8 but x is not congruence to either 1 or −1. (3 marks)

6. (i) We have 7x ≡ 21 mod 42 if and only if 7x + 42k = 21 for some

k ∈ Z, so this is the linear Diophantine equation we wish to solve.

We may divide throughout by 7 and obtain x+ 6k = 3. A particular

solution is (3, 0). The greatest common divisor of 1 and 6 is 1.

We may now use the theorem from the course that states that if a

particular solution to ax+bk = c is (x0, k0) then the general solution

to ax+ bk = c is

(x0 +

b

gcd(a, b)

t, k0 − a

gcd(a, b)

t).

Hence the general solution for our equation is (3 + 6t,−t), and so

x = 3 + 6t, t ∈ Z, is the solution. (6 marks)

(ii) 17 is a multiplicative inverse for 5 modulo 42, remember to actually

check this (1 mark)

(iii) Multiplying the congruence 5x ≡ 21 mod 42 by 17 we obtain x ≡

17 × 21 mod 42. We observe that 17 × 21 = 357, which has re-

mainder 21 on division by 42, hence x ≡ 21 mod 42. Therefore the

integers x satisfying the linear congruence are x = 21 + 42t, t ∈ Z.

(3 marks)

7. (i) The first result we need is that any integer n ≥ 2 can be written as a

product of primes. We can write this in the following equivalent way.

We have

n =

k∏

i=1

prii ,

where each ri ≥ 1 and the p1, . . . , pk are distinct primes. Then it is

clear that

n2 =

k∏

i=1

p2rii .

Another result we need from the course is that

φ(n) = φ(

k∏

i=1

prii ) =

k∏

i=1

(pi − 1)pri−1i ,

we may also use this formula for φ(n2), observe:

φ(n2) = φ(

k∏

i=1

p2rii ) =

k∏

i=1

(pi − 1)p2ri−1i .

At this point we divide φ(n2) by n, express this in terms of primes,

then we observe that it is equal to φ(n) (actually write it out and

check this in an exam). (5 marks)

(ii) If

φ(n) = φ(

k∏

i=1

prii ) =

k∏

i=1

(pi − 1)pri−1i = 11,

then since 11 is prime, precisely one of the (pi−1)pri−1i terms is equal

to 11. Now 11 is prime therefore either (pi − 1) = 11 or pri−1i = 11.

Now we rule out each case by a contradiction. If (pi − 1) = 11 then

pi = 12, which isn’t prime, a contradiction. If p

ri−1

i = 11 then ri = 2

and pi = 11, but then φ(n) will be divisible by φ(11

2) = 10 × 11,

which is too large to be 11, which is again a contradiction. The

conclusion is that there is no integer with φ(n) = 11. (5 marks)

8. (i) 7 is prime and so Fermat’s Little Theorem will tell us that when 7

does not divide n then n7−1 = n6 will be congruent to 1 modulo 7.

Therefore 1012 = 1006 will have remainder 1 on division by 7, because

7 does not divide 100. (5 marks)

(ii) (We cannot use Fermat because 28 is not prime, and we cannot use

Euler because 10 is not coprime to 28.) We can use the method of

successive squaring. 102 = 100 ≡ 16 mod 28, 104 ≡ 162 = 256 ≡

−24 ≡ 4 mod 28, 108 ≡ 42 = 16 mod 28. Thus 1012 ≡ 4× 16 =

64 ≡ 8 mod 28. (5 marks)

Mock assessment

1. (i) Write down the negation of the statement

∀n ∈ Z, if 3n+ 2 is odd , then n is odd .

Prove that the statement is true.

(ii) Use mathematical induction to prove that for all n ∈ N, 3 divides

4n + 2.

(10 marks)

2. (i) Let A,B,C and D be sets. Prove that

(A\C)× (B\D) ⊆ (A×B)\(C ×D).

Give an example where (A\C)× (B\D) 6= (A×B)\(C ×D).

(In this question you may assume that if S = ∅ or T = ∅, then

S × T = ∅.)

(ii) Let A be a denumerable set and f : R → A be a function. Prove

that f is not injective.

(10 marks)

3. (i) Let f : N → N be defined by f(n) = n2 − n + 1. Show that f is

injective. Is f surjective? Explain your answer.

(ii) Explain why the set of even integers and the set {k2 : k ∈ Z} are

equipotent. (You may state without proof any results from the lecture

notes.)

(10 marks)

4. (i) Let R be a relation defined on a set X. We define Rc to be the

relation where

xRcy ⇐⇒ (x, y) /∈ R.

Prove that R is symmetric =⇒ Rc is symmetric.

(ii) If R is an equivalence relation, must Rc be an equivalence relation?

Give a proof or counterexample. If you give a counterexample, also

determine whether Rc is reflexive, symmetric, or transitive for your

counterexample.

(10 marks)

5. (i) Let p be a prime. Prove that if x2 ≡ 1 mod p then either x ≡ 1

mod p or x ≡ −1 mod p. You may use results from the course

provided they are explicitly stated.

(ii) Let p be a prime. How many congruence classes [x]p are there such

that [x2]p = [1]p?

(iii) Let m ≥ 2 be an integer. If x2 ≡ 1 mod m must x ≡ ±1 mod m?

Give a proof or counterexample.

(10 marks)

6. (i) Find all solutions x ∈ Z to the linear congruence

7x ≡ 21 mod 42,

by reducing the problem to a linear Diophantine equation in two un-

knowns. You may use results from the course provided they are ex-

plicitly stated.

(ii) Find a multiplicative inverse for 5 modulo 42, you do not need to

explain your method.

(iii) Hence or otherwise find all x ∈ Z such that

5x ≡ 21 mod 42.

(10 marks)

7. (i) Let n ≥ 2 be an integer. Show that

φ(n2)

n

= φ(n),

where φ is Euler’s phi-function. You may use results from the course

provided they are explicitly stated, including the formula for φ(n).

(ii) Is there an integer n with φ(n) = 11? Justify your answer.

(10 marks)

8. (i) Use Fermat’s Little Theorem or Euler’s Theorem to calculate the

remainder of 1012 on division by 7.

(ii) Calculate the remainder of 1012 on division by 28, showing your work-

ing.

(10 marks)

Solutions

1. (i) The negation is ∃n ∈ Z, 3n+ 2 is odd and n is even. (1 mark)

We prove the original statement using proof by contradiction. Assume

the negation is true. Since n is even we can write n = 2k for some

k ∈ Z. Then 3n+2 = 6k+2 = 2(3k+1) is even because 3k+1 ∈ Z.

This contradicts our assumption that 3n + 2 is odd. Therefore the

statement is true. (4 marks)

(ii) Let P (n) be the statement 3 divides 4n + 2.

Base case: P (1) is true because 3 divides 41 + 2 = 6.

Inductive step: Let k ∈ N and assume P (k) is true, ie. 3 divides

4k + 2. Then 4k + 2 = 3m for some m ∈ Z. We have 4k+1 + 2 =

4.4k + 2 = 4(3m − 2) + 2 = 3(4m − 2) and this is divisible by 3

because 4m− 2 ∈ Z. Therefore P (k + 1) is true.

By induction, P (n) is true for all n ∈ N. (5 marks)

2. (i) Let (x, y) ∈ (A\C) × (B\D). Then x ∈ A\C and y ∈ B\D.

Therefore (x, y) ∈ A × B and (x, y) /∈ C × D. Hence (x, y) ∈

(A×B)\(C ×D) and (A\C)× (B\D) ⊆ (A×B)\(C ×D).

(5 marks)

If A = {1, 2}, B = {3, 4}, C = {1}, D = {3} we have

(A\C)×(B\D) = {(2, 4)},(A×B)\(C×D) = {(1, 4), (2, 3), (2, 4)}.

(1 mark)

(ii) Let A be a denumerable set and f : R → A be a function. Assume

that f is injective. Let g : R → Imf be defined by g(x) = f(x)

for all x ∈ R. Then g is surjective and injective and so g is a

bijection. Therefore R is equipotent with the image of f . Since

A is denumerable Imf is countable. his contradicts the fact that R

is uncountable. Therefore f is not injective. (4 marks)

3. (i) Assume n,m ∈ N. We have

f(n) = f(m)

⇒ n2 − n+ 1 = m2 −m+ 1

⇒ n2 −m2 = n−m

⇒ (n−m)(n+m) = n−m.

Therefore n = m or n + m = 1. Since n,m ∈ N we can’t have

n+m = 1. Hence n = m and f is injective. (4 marks)

We can see that f is not surjective because f(1) = 1, f(2) = 3 and

f(n) > n2 + 1 > 4 for all n > 2. Therefore 2 is not in the image of

f . (2 marks)

(ii) To show the sets are equipotent we need to find a bijection between

them. Let A = {2k : k ∈ Z} and B = {k2 : k ∈ Z}. A and B are

infinite subsets of the denumerable set Z and therefore they are both

denumerable. Hence there exist bijections f : N→ A and g : N→ B.

The inverse of f is also a bijection. The map g ◦ f−1 : A → B is

the composite of two bijections and therefore it is a bijection. By

definition A and B are equipotent. (4 marks)

4. (i) We need to show xRcy =⇒ yRcx. So assuming xRcy we have

(x, y) /∈ R by definition. SinceR is symmetric we must have (y, x) /∈

R. Then by definition we have yRcx, as required. (5 marks)

(ii) A counterexample is when R is the equivalence relation = on Z.

Then Rc is precisely the relation 6=. Now 1 = 1 and so we do not

have 1 6= 1, so 6= is not reflexive. We have already shown that 6= is

symmetric because = is. Finally, 6= is not transitive because 1 6= 2,

2 6= 1, but it is not the case that 1 6= 1. (5 marks)

5. (i) We observe x2 − 1 ≡ 0 mod p and therefore p divides x2 − 1 =

(x− 1)(x+1). Euclid’s property of primes states that if p divides ab

then either p divides a or p divides b. Therefore p divides (x− 1) or

p divides (x+1). Therefore x− 1 ≡ 0 mod p or x+1 ≡ 0 mod p.

Rearranging these congruences, we obtain the result required. (5

marks)

(ii) If p = 2 then there is only one congruence class namely [1]2. If p ≥ 3

is prime then there are two congruence classes [1]p and [−1]p by the

previous part. (2 marks)

(iii) A counterexample is m = 8 and x = 3, we observe that x2 = 9 ≡ 1

mod 8 but x is not congruence to either 1 or −1. (3 marks)

6. (i) We have 7x ≡ 21 mod 42 if and only if 7x + 42k = 21 for some

k ∈ Z, so this is the linear Diophantine equation we wish to solve.

We may divide throughout by 7 and obtain x+ 6k = 3. A particular

solution is (3, 0). The greatest common divisor of 1 and 6 is 1.

We may now use the theorem from the course that states that if a

particular solution to ax+bk = c is (x0, k0) then the general solution

to ax+ bk = c is

(x0 +

b

gcd(a, b)

t, k0 − a

gcd(a, b)

t).

Hence the general solution for our equation is (3 + 6t,−t), and so

x = 3 + 6t, t ∈ Z, is the solution. (6 marks)

(ii) 17 is a multiplicative inverse for 5 modulo 42, remember to actually

check this (1 mark)

(iii) Multiplying the congruence 5x ≡ 21 mod 42 by 17 we obtain x ≡

17 × 21 mod 42. We observe that 17 × 21 = 357, which has re-

mainder 21 on division by 42, hence x ≡ 21 mod 42. Therefore the

integers x satisfying the linear congruence are x = 21 + 42t, t ∈ Z.

(3 marks)

7. (i) The first result we need is that any integer n ≥ 2 can be written as a

product of primes. We can write this in the following equivalent way.

We have

n =

k∏

i=1

prii ,

where each ri ≥ 1 and the p1, . . . , pk are distinct primes. Then it is

clear that

n2 =

k∏

i=1

p2rii .

Another result we need from the course is that

φ(n) = φ(

k∏

i=1

prii ) =

k∏

i=1

(pi − 1)pri−1i ,

we may also use this formula for φ(n2), observe:

φ(n2) = φ(

k∏

i=1

p2rii ) =

k∏

i=1

(pi − 1)p2ri−1i .

At this point we divide φ(n2) by n, express this in terms of primes,

then we observe that it is equal to φ(n) (actually write it out and

check this in an exam). (5 marks)

(ii) If

φ(n) = φ(

k∏

i=1

prii ) =

k∏

i=1

(pi − 1)pri−1i = 11,

then since 11 is prime, precisely one of the (pi−1)pri−1i terms is equal

to 11. Now 11 is prime therefore either (pi − 1) = 11 or pri−1i = 11.

Now we rule out each case by a contradiction. If (pi − 1) = 11 then

pi = 12, which isn’t prime, a contradiction. If p

ri−1

i = 11 then ri = 2

and pi = 11, but then φ(n) will be divisible by φ(11

2) = 10 × 11,

which is too large to be 11, which is again a contradiction. The

conclusion is that there is no integer with φ(n) = 11. (5 marks)

8. (i) 7 is prime and so Fermat’s Little Theorem will tell us that when 7

does not divide n then n7−1 = n6 will be congruent to 1 modulo 7.

Therefore 1012 = 1006 will have remainder 1 on division by 7, because

7 does not divide 100. (5 marks)

(ii) (We cannot use Fermat because 28 is not prime, and we cannot use

Euler because 10 is not coprime to 28.) We can use the method of

successive squaring. 102 = 100 ≡ 16 mod 28, 104 ≡ 162 = 256 ≡

−24 ≡ 4 mod 28, 108 ≡ 42 = 16 mod 28. Thus 1012 ≡ 4× 16 =

64 ≡ 8 mod 28. (5 marks)