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 final two pages are for scratch work. If you need extra paper, it will be provided.
• Show all necessary steps. A solution without sufficient justification 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 scientific 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 field. (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 find it helpful to recall the definition of Z/pZ.)
(b) Let a, b ∈ Z. We define a · b = ab. Prove that this notion is well-defined.
(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 find 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 defines an elliptic curve E over the field 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 define an elliptic curve over the finite field 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

Preparing to load PDF file. please wait...

0 of 0
100%
Elementary Number Theory: Practice Final Exam