Number Theory Homework 6 With Solutions


Introduction to Number Theory

MATH 506

Spring 2014 - Chris Pinner- 12387

MWF 9:30-10:20 CW120


Chris 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 277-1, 1080+1 and 3031-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

Printable 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 32+
42=52) 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”

    -->

Leave a Comment

Your email address will not be published. Required fields are marked *