Course Title | ## Number Theory | ||

Course Code | ## MH3210 | ||

Offered | Study Year 3, Semester 1 | ||

Course Coordinators | Frederique Elise Oggier (Assoc Prof) | frederique@ntu.edu.sg | 6513 2026 |

Bernhard Schmidt (Prof) | bernhard@ntu.edu.sg | 6513 2009 | |

Pre-requisites | MH1300 | ||

AU | 4 | ||

Contact hours | Lectures: 39, Tutorials: 12 | ||

Approved for delivery from | AY 2021/22 semester 1 | ||

Last revised | 27 Oct 2021, 14:20 |

This course aims to provide a first discovery of number theory using elementary techniques (that is techniques mostly built from scratch during the course). You will learn fundamental results on the divisibility of integers, on prime numbers, on Diophantine equations, and hear about famous conjectures in number theory. You will also practice working with congruences modulo an integer, and solving polynomial congruences and systems of linear congruences. This knowledge will be useful to you if you plan to take a course on abstract algebra, or if you are interested in applications of mathematics to cryptography.

Upon successfully completing this course, you should be able to:

- State fundamental results in number theory.
- Compute modulo an integer.
- Solve linear diophantine equations and linear congruences.
- Prove results in number theory involving short reasoning.
- Solve polynomial congruences and systems of linear congruences.
- Compute primitive roots.
- Compute Legendre symbol.

The Euclid division algorithm and its extended version, and to use them to compute the greatest common divisor of integers.

Bezout identity.

The existence and unicity of writing an integer in a given basis.

Fundamental Theorem of Arithmetic.

Existence of an infinity of primes.

Linear diophantine equations.

Modular arithmetic.

Linear congruences and the Chinese Remainder Theorem.

Primality testing.

Primitive roots.

Legendre symbol.

The law of quadratic reciprocity.

Component | Course ILOs tested | SPMS-MAS Graduate Attributes tested | Weighting | Team / Individual | Assessment Rubrics |
---|---|---|---|---|---|

Continuous Assessment | |||||

Mid-semester Quiz | |||||

Short Answer Questions 1 | 4, 5, 6, 7 | 1. a, c3. a | 20 | individual | See Appendix for rubric |

Short Answer Questions 2 | 2, 3, 4, 5 | 1. a, c3. a | 20 | individual | See Appendix for rubric |

Examination (2.0 hours) | |||||

Short Answer Questions | 1, 2, 3, 4, 5, 6, 7 | 1. a, c2. c3. a | 60 | individual | See Appendix for rubric |

Total | 100% |

These are the relevant SPMS-MAS Graduate Attributes.

## 1. Competence

a. Independently process and interpret mathematical theories and methodologies, and apply them to solve problems

c. Discover patterns by abstraction from examples

## 2. Creativity

c. Develop new applications of existing techniques

## 3. Communication

a. Present mathematics ideas logically and coherently at the appropriate level for the intended audience

You will have the opportunity to discuss your understanding of results in number theory, of the techniques taught to execute different types of computations (modulo an integer, solving linear equations) and to prove results (a number of them related to divisibility properties) during lectures via group discussions, during which feedback will be provided by peers and the lecturer.

You will also have the option to present solutions of your exercises during the tutorials, which will receive feedback from the lecturer.

Midterm assessments will be graded and feedback will be provided for each student on the area(s) that should be improved (if any) and those which are already satisfactory.

After the exam period, a feedback on the final exam will be uploaded on NTULearn.

Lectures (39 hours) | Proofs (e.g. for proving divisibility properties of integers) are done on the board, this is to make sure that the pace is appropriate and you get to see how every step is done. Small exercises are provided during the lecture, to be discussed in groups, to make sure that you have understood the new topic/definition before moving on. This also gives you the opportunity to practice computations in class (e.g. modular arithmetic, solving linear equations). Whenever possible, plots/animations will be provided to give you a visualization of abstract functions/concepts (e.g. fundamental results in number theory). |

Tutorials (12 hours) | Exercises will belong to typically two categories: small proofs, so you get trained in formulating and proving results in number theory (e.g. for providing divisibility properties of integers), and computations, so you develop the skills to be able to work with modular arithmetic, solve linear integer/congruence equations, systems of congruences. |

Elementary Number Theory, by G. A. Jones and M. Jones, Springer Undergraduate Mathematics Series.

This book is recommended and it can be accessed via NTU library.

ISBN-13: 978-3540761976

ISBN-10: 3540761977Elementary Number Theory, by Rosen. This is book contains broadly the same content, with more exercises, in particular elementary ones, however it is difficult to access it via NTU library (requires the installation of a 3rd party DRM and even after that, only 2 students at a time can access the book).

ISBN-10: 129203954X

ISBN-13: 978-1292039541

As for every course, please try to be as ready as possible before coming to class. This means you should have tried to solve the tutorial exercises, and reminded yourself of the topic taught.

Good academic work depends on honesty and ethical behaviour. The quality of your work as a student relies on adhering to the principles of academic integrity and to the NTU Honour Code, a set of values shared by the whole university community. Truth, Trust and Justice are at the core of NTUâ€™s shared values.

As a student, it is important that you recognize your responsibilities in understanding and applying the principles of academic integrity in all the work you do at NTU. Not knowing what is involved in maintaining academic integrity does not excuse academic dishonesty. You need to actively equip yourself with strategies to avoid all forms of academic dishonesty, including plagiarism, academic fraud, collusion and cheating. If you are uncertain of the definitions of any of these terms, you should go to the Academic Integrity website for more information. Consult your instructor(s) if you need any clarification about the requirements of academic integrity in the course.

Instructor | Office Location | Phone | |
---|---|---|---|

Frederique Elise Oggier (Assoc Prof) | MAS05-13 | 6513 2026 | frederique@ntu.edu.sg |

Bernhard Schmidt (Prof) | SPMS-MAS-05-24 | 6513 2009 | bernhard@ntu.edu.sg |

Week | Topic | Course ILO | Readings/ Activities |
---|---|---|---|

1 | The Euclid division algorithm, the existence and unicity of writing an integer in a given basis. | 4, 7 | Theorem 1.10 (Rosen)or Theorem 1.1 (Jones) |

2 | Existence of an infinity of primes. Bezout identity. | 4, 7 | Theorem 3.1 (Rosen), Theorem 2.6 (Jones), Theorem 3.8 and Corollary 3.8.1 (Rosen), or Theorem 1.7 (Jones) |

3 | The extended Euclid algorithm, and to use them to compute the greatest common divisor of integers. Fundamental Theorem of arithmetic. | 4, 7 | Theorem 3.14 (Rosen) or Theorem 1.6 (Jones), Theorem 3.15 (Rosen)or Theorem 2.3 (Jones) |

4 | Modular arithmetic, modular exponentiation, | 5, 6 | Theorem 3.23 and 3.24 (Rosen) or Theorem 3,7 (Jones), Theorem 4.1, 4.2 (Rosen)or Lemma 3.1 (Jones) |

5 | Linear congruences and the Chinese Remainder Theorem. | 3, 5, 6 | Theorem 4.11 (Rosen)or Theorem 3.7 (Jones), Theorem 4.12, Theorem 4.13 (Rosen)or Theorem 3.10 (Jones) |

6 | Euler function, and Euler's and Wilson's theorems | 4, 5 | Theorem 5.3 (Jones), Theorem 6.13 (Rosen), Corollary 4.5 (Jones), Theorem 6.1 (Rosen) |

7 | Applications of Euler's Theorem, e.g. RSA | 4, 5 | section 8.4 p. 323-324 by Rosen or p. 95 by Jones |

8 | Existence of primitive roots | 2, 5 | Theorems 6.5, 6.7, 6.11 (Jones), Theorems 9.1, 9.8, 9.10, 9.15 (Rosen) |

9 | Applications of primitive roots | 2, 5 | section 6.6 (Jones), chapter 10 (Rosen) |

10 | Quadratic residues and Legendre symbol | 1, 5 | chapter 11 (Rosen), chapter 7 (Jones) |

11 | Legendre symbol and quadratic reciprocity | 1, 4, 5 | chapter 11 (Rosen), chapter 7 (Jones) |

12 | Jacobi symbol | 1, 5 | chapter 11 (Rosen), chapter 7 (Jones) |

13 | Pythagorean triples | 4 | chapter 11 (Jones), section 13.1 (Rosen) |

The assessment comprise short answer questions, of two types: short reasoning and computations.

Assessment criteria include:

- right answer,
- proper arguments and justifications,
- details provided.

To score a high mark, it is needed that the right answer is provided with a justification. It is also possible to have a high score while making some small mistake, if the argumentation is clear and the mistake is coming from for example a typo, or an inattention mistake.

A right answer with no justification whatsoever will result in a pass mark, enough evidence of understanding even with a wrong answer will result in a pass mark.

A wrong answer with no argument, or a wrong answer with wrong justification, or no answer will result in a fail mark.The assessment comprise short answer questions, of two types: short reasoning and computations.

Assessment criteria include:

- right answer,
- proper arguments and justifications,
- details provided.

To score a high mark, it is needed that the right answer is provided with a justification. It is also possible to have a high score while making some small mistake, if the argumentation is clear and the mistake is coming from for example a typo, or an inattention mistake.

A right answer with no justification whatsoever will result in a pass mark, enough evidence of understanding even with a wrong answer will result in a pass mark.

A wrong answer with no argument, or a wrong answer with wrong justification, or no answer will result in a fail mark.The assessment comprise short answer questions, of two types: short reasoning and computations.

Assessment criteria include:

- right answer,
- proper arguments and justifications,
- details provided.

To score a high mark, it is needed that the right answer is provided with a justification. It is also possible to have a high score while making some small mistake, if the argumentation is clear and the mistake is coming from for example a typo, or an inattention mistake.

A right answer with no justification whatsoever will result in a pass mark, enough evidence of understanding even with a wrong answer will result in a pass mark.

A wrong answer with no argument, or a wrong answer with wrong justification, or no answer will result in a fail mark.