# Number Theory Homework 6 With Solutions

## Introduction to Number Theory

## MATH 506

## Spring 2014 - Chris Pinner- 12387

MWF 9:30-10:20 CW120Chris Pinner

CW205

pinner@math.ksu.edu

532-0587

Office Hours (tentative): MWF 10:30 & other times by appt.

Home-Page: http://www.math.ksu.edu/~pinner/math506

Updates

Advanced Help Session Schedule

Homeworks

**Hw1: Ch0**: 6,12. **1.1: **8,10,16,17. **1.2: **6,8,12,18,20,33,34. (Due Fri Jan 31). (HW1 Questions)**Hw2: 1.2:** 14,16,30. **1.3: **4,6,21,28. (Due Fri Feb 7).**Hw3: 1.****4:** 2,6,24,26.**1.5:** 2,4,16,22,32,36,45,47. (Due Fri Feb 14).**Hw4: 2.4:** 22,28,32,38,40,42,51. **2.3:** 42. **1.6: **18,19,39,44. (Due Fri Feb 21).**Hw5:**Homework 5 Questions (Due Fri Feb 28).**Hw6: 2.2:** 2,4,18,23. **2.3:** 22,28,30. **7.1: **20,22,26,28,30. (Due Fri Mar 7).**Hw7: 2.3:** 4,20,34,40. **2.4:** 16,52. **2.6: **10,32. **3.4: **16,17,18,19.

A) Give a non-trivial factor for 2^{77}-1, 10^{80}+1 and 30^{31}-1 (Due Fri Mar 14).**Hw8: 2.5:** 4,11,17,19. **2.6: **18,20,24,26,28,30,34,43,46. (Due Fri Mar 28).**HW9: 3.1: **8,14,18,30,36,40,44.** 3.2:** 8,10,13,20,25,26. (Due Fri Apr 4).**HW10: 3.6:** 2,10,12,17,18,20. **3.5: **22,36,42,44.** 3.2:** 22,24. **3.3:** 30. (Due Apr 11).**HW11: 4.1: **26,28,34,42,43. **4.3: **28,30,44. **4.2: **2,8,10,16,32. (Due Apr 18).**HW12: 4.2: **37,51. **4.3:** 4,6,8,20,36,45,47. (Due Apr 25).**HW13:****4.4:** 4,8,13,25,26. **4.5: **20,30. **6.2: **20,26. (Due May 2).**HW14:****6.3: **4,8,13,16,26. **6.4: **6,14,36. **5.4:** 16,22. (Due May 14?).

Exam Solutions:

Blank Exam 1 Solutions

Blank Exam 2 Solutions

Blank Exam 3 Solutions

Blank Final Exam Solutions

Syllabus

Text: Elementary Number Theory, Charles vanden Eynden, 2nd edition, Waveland Press, ISBN 1-57766-445-0 (McGraw-Hill ISBN 0-07232-571-2 is the same edition).

Course Outline

Number theory is essentially the study of the natural numbers 1,2,3,...and their properties. It is one of the oldest branches of mathematics but continues to be an active area of research. For example a major modern day application is cryptography (the National Security Agency is the largest employer of Number Theorists in the country). Its problems, often simple to state, have in many cases remained unsolved for centuries.

We should cover much of Vanden Eynden. In particular proof by induction, divisibility, primes, uniqueness of factorization, congruences, Chinese Remainder Theorem, Cryptography, Pythagorean triples (eg 3

^{2}+4

^{2}=5

^{2}) and other Diophantine equations, Perfect Numbers (eg 6=1+2+3 is the sum of its proper divisors), rational versus irrational, arithmetic functions, rational approximation & continued fractions (eg pi is close to 22/7, 355/113 is better; how do we obtain approximations like these?), quadratic congruences & quadratic reciprocity. We may occasionally include material outside of the text.

Prequisites

MATH 220 & 221 recommended but all that is required is a sound knowledge of College Algebra and some mathematical maturity.

Grade Scheme:

Homework (130 points)

Exam 1 Wed Feb 19 (100 points)

Exam 2 Wed Mar 26 (100 points)

Exam 3 Wed Apr 18 (100 points)

Final Exam Wed May 14 11:50-1:40 (150 points).

Exam dates are tentative!

Assignments

Homework will be assigned in class (due in the HW box by 5pm on the Friday of the following week). You will generally have about a week to complete the assignment. Don't leave your homework to the last minute (many of the questions will involve proofs or may require extended thought). Show all your work. Include your name and Math 506 on the front. The lowest homework score will be dropped.

General Information

If you have any condition such as a physical or learning disability, which will make

it difficult to carry out the work as I have outlined it or which will require academic accommodations, please notify me in the first two weeks of class. There will be no late homework or make-up exams. If you have to miss a test for a valid reason then your course grade will be determined from your remaining work (notify me as soon as possible).

Some Useful Dates

Jan 20 - MLK Holiday

Feb 10 - Last day for 100% refund

Feb 17 - Last day for 50% refund

Feb 25 - Last day to drop without a W

Mar 17-21 - Spring Break

Mar 31 - Last day to drop with a W

May 9- Last Day of Class.

Mandatory Syllabi Statements

See mandatory syllabi statements concerning

1. Academic honesty. 2. Accommodations for students with disabilities. 3. Expectations for classroom conduct.

Old Exams:

Spring2012:

Blank Exam 1 Solutions

Blank Exam 2 Solutions

Blank Exam 3 Solutions

Blank Final Exam Solutions

Spring2008:

Blank Exam 1 Solutions

Blank Exam 2 Solutions

Blank Exam 3 Solutions

Blank Final Exam Solutions

Spring2006:Blank Exam 1 Solutions

Blank Exam 2 Solutions

Blank Exam 3 Solutions

Blank Final Exam Solutions

Spring2004:

Exam 1 Solutions: pg1: pg2: pg3:

Exam 2 Solutions: pg1: pg2: pg3:

Exam 3 Solutions: pg1: pg2: pg3:

Final Exam Solutions: pg1: pg2: pg3: pg4:

Spring2003:

Exam 1 Solutions: pg1: pg2: pg3

Exam 2 Solutions: pg1: pg2: pg3

Exam 3 Solutions: pg1: pg2: pg3

Final Exam Solutions: pg1: pg2: pg3: pg4:

Some Number Theory Things

## Math 4150, Introduction to Number Theory

### Spring 2011

**Instructor:**Matt Baker**Time and place:**MWF 2:05-2:55, Skiles 270**E-mail:**mbaker@math.gatech.edu**Office:**Skiles 212**Office Hours:**Monday 1-2 and Wednesday 11-12

** If you haven't already done so, please fill out the Online Course Survey. **

### Exam schedule:

- Midterm #1: Monday, February 21
- Midterm #2: Friday, March 18
- Midterm #3: Monday, April 18
- Final exam: Friday, May 6 11:30-2:20 in Skiles 270

### Topics for Midterm 3:

- Quadratic residues and nonresidues, Legendre symbol, Euler's criterion, (-1/p) and (2/p), Law of Quadratic Reciprocity, computing modular square roots (excluding Cipolla's algorithm), flipping coins electronically, Pepin's test, Jacobi symbol, evaluating Legendre and Jacobi symbols, Euler pseudoprimes, the Solovay-Strassen test.

### Topics for Midterm 2:

- Strong pseudoprimes, Miller-Rabin test, RSA cryptosystem, RSA digital signatures, Diffie-Hellman key exchange, El Gamal cryptosystem, Order of an integer mod m, primitive roots, discrete logarithms and index arithmetic, Lucas' converse of Fermat's Little Theorem, the power residue theorem.

### Topics for Midterm 1:

- Divisibility, prime numbers, GCD's, (extended) Euclidean algorithm, Fundamental Theorem of Arithmetic, linear Diophantine equations, congruences, Chinese Remainder Theorem, divisibility tests, ISBN's, Wilson's theorem, Fermat's Little Theorem, pseudoprimes and Carmichael numbers, Euler's theorem (including FLT+CRT improvements), Euler's phi-function.

### Ninth homework assignment:

(due Friday, April 15)- Read sections 11.3-11.4 in the book
- Section 11.1 #21, 35, 45, 48
- Section 11.1 Computations and Explorations #9
- Section 11.1 Programming Project #3
- Section 11.2 #5
- Section 11.3 #1,5
- Section 11.4 #1,5
- Section 11.4 Computations and Explorations #1
- Section 11.4 Programming Project #1
- Solutions to Homework 9

### Eighth homework assignment:

(due Wednesday, April 6)- Read sections 11.1-11.2 in the book
- Section 11.1 #5, 7, 13, 14, 20, 29, 44 (Bonus: #18, 26)
- Section 11.2 #1, 2, 3, 6, 7
- Solutions to Homework 8

### Seventh homework assignment:

(due Wednesday, March 16)### Sixth homework assignment:

(due Wednesday, March 9)- Read sections 8.6, 9.1, 9.5, 10.2 in the book
- Section 8.6 #6
- Section 9.1 #1,8,15,22 (optional: #20)
- Section 9.1 Computations and Explorations #1
- Section 9.5 #2,3
- Section 9.5 Programming Project #2
- Section 10.2 #1,4 (optional: #7)
- Section 10.2 Programming Projects #1,2
- Solutions to Homework 6

### Fifth homework assignment:

(due Wednesday, March 2)- Read sections 6.2, 8.1, 8.4, 8.6 (Diffie-Hellman Key Exchange) in the book
- Section 6.2 #12, 13
- Section 8.4 #2, 8, 13, 14
- Section 8.6 #2
- Section 6.2 Programming Project #4
- Section 8.4 Programming Projects #1-4
- Solutions to Homework 5

### Fourth homework assignment:

(due Wednesday, February 16)- Read sections 6.1, 6.2, 6.3, and 7.1 in the book (excluding Miller's Test in 6.2)
- Section 6.1 #12, 19, 20, 22
- Section 6.2 #2, 7, 8, 18 (Bonus: #6 )
- Section 6.3 #3, 6, 10, 20
- Section 7.1 #3, 6, 8
- Solutions to Homework 4

### Third homework assignment:

(due Wednesday, February 9)- Read sections 4.3, 5.1, 5.2, and 5.5 in the book.
- Section 4.2 #8, 14, 18
- Section 4.3 #7, 10, 12, 19, 27 (Bonus: #14)
- Section 5.1 #19, 22
- Section 5.2 #2dijkno, 13
- Section 5.5 #12, 13
- Solutions to Homework 3

### Second homework assignment:

(due Wednesday, February 2)- Read sections 3.6-3.7 and 4.1-4.2 in the book
- Section 3.5 #14,29,36,39,42,71
- Section 3.7 #2,6
- Section 4.1 #5,6,30,34
- Solutions to Homework 2

### First homework assignment:

(due Wednesday, January 26)- Read sections 3.1-3.5 in the book
- Section 3.1 #7
- Section 3.2 #3
- Section 3.3 #16
- Section 3.4 #2,4,21 + Bonus problem #22
- Section 3.5 #6,10,23,24,25,26
- Solutions to Homework 1

### Course text:

- (6th edition), by Kenneth H. Rosen

### Course outline:

- This course is an introduction to number theory and its applications to modern cryptography. Number theory, which is one of the oldest branches of mathematics, is the study of the many fascinating properties of integers. For example, we will look at prime numbers and their distribution, modular (``clock'') arithmetic, factoring and primality testing, encryption/decryption techniques based on number theory, and Diophantine equations.

### Exams:

- There will be 3 in-class midterm exams during the course of the semester, plus a cumulative in-class final exam at the end of the course.

### Homework:

- Homework will be assigned on a regular basis.

### Grading Policy:

- The three midterm exams will each count for 20% of your grade, the final will count 30%, and homework will count 10%.

### Collaboration:

- On the homework sets, collaboration is both allowed and encouraged. However, you must write up yourself and understand your own homework solutions.

### Miscellany:

- If at any point during the semester you feel unsatisfied with some aspect of the course, please come talk to me about it! I am happy to make adjustments mid-stream if necessary.

### Useful links:

*This page was last modified on May 3, 2011 by Matt Baker.*

## 0 thoughts on “Number Theory Homework 6 With Solutions”

-->