# mpawliuk/MC-2018-NT

Some course materials for the 2018 Math Circle Number Theory course
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
joseph_game.py

# Introduction to Number Theory - Math Circle 2018

Instructor: Micheal Pawliuk (University of Calgary)
Summer 2018, Math Circle, Emory University
E-mail: mpawliuk+MC@gmail.com
Class Hours: M-Th 9-9:50 am (Lecture), 9:50-10:40 am (Problem Solving)

## Course Description:

This course will introduce students to elementary number theory. Students will first learn basic logic and the structure of mathematical statements. Then they will proceed through number systems, divisibility theory, and modular arithmetic. The students will also learn some applications of number theory such as solving Diophantine equations and RSA encryptions.

## Reference

This class will follow the schedule below and as a class we will build a mini-textbook together. You can find the ongoing textbook here:

https://www.overleaf.com/17625866ycbvqbpvnhsp

Students can also use the following resources:

# Schedule

## Week 1 - Introduction to Integers

### 1.1 Introduction

• Introduction of people in class
• Sample problems to pique interest in number theory
• Hotdogs come in pack of 10. Hotdog buns come in pack of 8. How much of each should you buy to not have any leftover hotdogs or buns?
• You have 2 containers with no markings. However, you know that container A can hold a max amount of 3 liters. Container B can hold a max amount of 4 liters. How to you make 1 liters? 10 liters? 15 liters?
• Given a number, check whether it is divisible by 2,3,5,9,11.
• Introduction to logic
• Conditional statements
• Biconditional statements
• Quantifiers

### 1.2 Number Systems

• Introduction to the number systems: N,Z,Q
• Define even and odd numbers and do some standard proofs
• Let n be an integer. Then n^2 is even if and only if n is even.
• Note that there are irrational numbers
• Shows that \sqrt{2} is irrational
• (Maybe start induction)

### 1.3 Induction, Composite and Primes

• Proofs by induction
• Introduction to divisibility
• Composite and Primes
• Existence of prime factorization
• Proof of infinite primes
• Mention the related topics for primes
• Finding primes: sieves, asymptotic function, etc.
• Efficient way to factorize integer
• Prime gaps

### 1.4 Division Algorithm (part 1)

• GCD and LCM
• Division Algorithm (maybe proof)
• Proof of existence
• Proof of uniqueness

## Week 2 - Classic Number Theory

### 2.1 Division Algorithm (part 2)

• Euclidean Algorithm
• GCD with Euclidean Algorithm (Proof)

### 2.2 Diophantine Equations

• Diophantine equation
• Using Euclidean Algorithm to solve Diophantine equations
• Find all solution to Diophantine equations

### 2.3 Fundamental Theorem of Arithmetic

• The Fundamental Theorem of Arithmetic and proof
• Consequences of the FTA

### 2.4 Modular Arithmetic

• Definition of congruence
• Definition of modulo
• Congruence class
• (Maybe equivalence relation)
• Modular arithmetic
• Test for divisibility (application modular arithmetic)

## Week 3 - Applications and Encryption

### 3.1 Chinese Remainder Theorem

• The Chinese Remainder Theorem (Story, Statement, and Proof)
• Generalize Chinese Remainder Theorem
• Example of application of CRT

### 3.2 Groups, Rings and Shifts

• Introduce groups and rings
• Z n and properties of Z n
• Wilson’s Theorem
• Elementary encryption

### 3.3 Phi Function

• Euler’s Phi-function
• Euler’s Theorem.
• Exponent modulo n
• RSA encryption

### 3.4 Discrete Logarithm Problem

• What is a Discrete Logarithm?
• Is it easy to solve?
• Diffie-Hellman Key Exchange