# Elementary Number Theory: Practice Final Exam

Download Elementary Number Theory: Practice Final Exam

## Preview text

Elementary Number Theory: Practice Final Exam

Summer 2016

Name:

July 31, 2016

Student ID:

Instructions

• This exam consists of 6 problems on 9 pages. The ﬁnal two pages are for scratch work. If you need extra paper, it will be provided.

• Show all necessary steps. A solution without suﬃcient justiﬁcation will not receive full credit.

• You may use Theorems from the lecture, unless stated otherwise. Please state clearly and explicitly any such results.

• Please write the solution in the space provided going to the back side if necessary.

• Write clearly and legibly. Points will be deducted if the solution or the logical sequence is not understood.

• A scientiﬁc calculator is allow as long as it can not be programmed.

Problem: 1

2

3

4

5

6 Total

Score:

1

Elementary Number Theory Final Exam, Page 2 of 9 1. Show that 1105 is a Carmichael number.

Sommer 2016

Elementary Number Theory Final Exam, Page 3 of 9

Sommer 2016

2. Find all solutions (x, y) ∈ Q2 to each of the following or prove that none exist. (a) x2 + y2 = 2 (b) x2 + y2 = 3

Elementary Number Theory Final Exam, Page 4 of 9

Sommer 2016

3. Let p be prime. In this problem do not use that Fp = Z/pZ is a ﬁeld. (You will essentially prove this result here.)

(a) For each a ∈ Z let a denote the equivalence class of a in Z/pZ. What exactly is a? (You may ﬁnd it helpful to recall the deﬁnition of Z/pZ.)

(b) Let a, b ∈ Z. We deﬁne a · b = ab. Prove that this notion is well-deﬁned.

(c) Let a ∈ Z such that p a. Prove that there exists b ∈ Z such that ab ≡ 1 (mod p).

Elementary Number Theory Final Exam, Page 5 of 9

Sommer 2016

4. In this problem you may use the fact that p = 53 = 22 · 13 + 1 is prime. (a) Show that ( p7 ) = 1. (b) Show that 3 is not a square modulo p. (c) Describe Tonelli’s algorithm and use it to ﬁnd all solutions to x2 ≡ 7 (mod p).

Elementary Number Theory Final Exam, Page 6 of 9

Sommer 2016

5. Suppose that x ∈ R \ Q. Let αn be as in the continued fraction expansion algorithm, meaning that if an = αn then [a0, a1, a2, . . .] is the continued fraction expansion of x.

(a) Suppose that αj = α for some j > . Prove that this implies that the continued fraction expansion of x is periodic. √

(b) Find the continued fraction expansion of 7.

Elementary Number Theory Final Exam, Page 7 of 9

Sommer 2016

6. Show that y2 = x3 + 1 deﬁnes an elliptic curve E over the ﬁeld Q of rational numbers. Recall that if E is given by y2 = x3 + ax2 + bx + c then ∆(E) = −4a3c + a2b2 + 18abc − 4b3 − 27c2 is the discriminant of E.

(a) Does the given equation deﬁne an elliptic curve over the ﬁnite ﬁeld Fp of p elements, for each p ∈ {2, 3, 5}? If so, determine the set E(Fp).

(b) Find E(Q)tor.

Elementary Number Theory Final Exam, Page 8 of 9

Sommer 2016

Elementary Number Theory Final Exam, Page 9 of 9

Sommer 2016

Summer 2016

Name:

July 31, 2016

Student ID:

Instructions

• This exam consists of 6 problems on 9 pages. The ﬁnal two pages are for scratch work. If you need extra paper, it will be provided.

• Show all necessary steps. A solution without suﬃcient justiﬁcation will not receive full credit.

• You may use Theorems from the lecture, unless stated otherwise. Please state clearly and explicitly any such results.

• Please write the solution in the space provided going to the back side if necessary.

• Write clearly and legibly. Points will be deducted if the solution or the logical sequence is not understood.

• A scientiﬁc calculator is allow as long as it can not be programmed.

Problem: 1

2

3

4

5

6 Total

Score:

1

Elementary Number Theory Final Exam, Page 2 of 9 1. Show that 1105 is a Carmichael number.

Sommer 2016

Elementary Number Theory Final Exam, Page 3 of 9

Sommer 2016

2. Find all solutions (x, y) ∈ Q2 to each of the following or prove that none exist. (a) x2 + y2 = 2 (b) x2 + y2 = 3

Elementary Number Theory Final Exam, Page 4 of 9

Sommer 2016

3. Let p be prime. In this problem do not use that Fp = Z/pZ is a ﬁeld. (You will essentially prove this result here.)

(a) For each a ∈ Z let a denote the equivalence class of a in Z/pZ. What exactly is a? (You may ﬁnd it helpful to recall the deﬁnition of Z/pZ.)

(b) Let a, b ∈ Z. We deﬁne a · b = ab. Prove that this notion is well-deﬁned.

(c) Let a ∈ Z such that p a. Prove that there exists b ∈ Z such that ab ≡ 1 (mod p).

Elementary Number Theory Final Exam, Page 5 of 9

Sommer 2016

4. In this problem you may use the fact that p = 53 = 22 · 13 + 1 is prime. (a) Show that ( p7 ) = 1. (b) Show that 3 is not a square modulo p. (c) Describe Tonelli’s algorithm and use it to ﬁnd all solutions to x2 ≡ 7 (mod p).

Elementary Number Theory Final Exam, Page 6 of 9

Sommer 2016

5. Suppose that x ∈ R \ Q. Let αn be as in the continued fraction expansion algorithm, meaning that if an = αn then [a0, a1, a2, . . .] is the continued fraction expansion of x.

(a) Suppose that αj = α for some j > . Prove that this implies that the continued fraction expansion of x is periodic. √

(b) Find the continued fraction expansion of 7.

Elementary Number Theory Final Exam, Page 7 of 9

Sommer 2016

6. Show that y2 = x3 + 1 deﬁnes an elliptic curve E over the ﬁeld Q of rational numbers. Recall that if E is given by y2 = x3 + ax2 + bx + c then ∆(E) = −4a3c + a2b2 + 18abc − 4b3 − 27c2 is the discriminant of E.

(a) Does the given equation deﬁne an elliptic curve over the ﬁnite ﬁeld Fp of p elements, for each p ∈ {2, 3, 5}? If so, determine the set E(Fp).

(b) Find E(Q)tor.

Elementary Number Theory Final Exam, Page 8 of 9

Sommer 2016

Elementary Number Theory Final Exam, Page 9 of 9

Sommer 2016

## Categories

## You my also like

### NCERT Solutions for Class 6 Social Science Geography

75.1 KB22.1K3.3K### AP Japanese Language and Culture Exam Overview 2021

3.9 MB3.4K1.3K### Fractions 3 Go deeper investigations

600.4 KB2.6K998### Multiples of Unit Fractions

74.5 KB3.7K1.7K### SAFETY DATA SHEET (SDS) Coated Abrasives

702.1 KB4.6K1K### Models For Fractions

582.7 KB9K3.5K### Using MATLAB to find a Partial Fraction Expansion

221.5 KB31.9K8.6K### Calculus for Computer Scientists Lecture Notes

1.5 MB25.2K4K### Module 02 Laplace Transforms, Transfer Functions & ODEs

1.1 MB15.6K2.7K