Congruence In Elementary Number Theory And Its Applications åä½å¨åçæ°è®ºä¸çåºç¨

Baishi Wang 10114556

Supervisor: Dr. Ignazio Longhi

Contents 1 Introduction 2

2 Literature Review 3

3 Methodology 5

4 Chapter 1 6 4.1 Divisibility and Prime Number . . . . . . . . . . . . . . . . . . . . . . 6 4.2 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5 Chapter 2: Divisibility test 10 5.1 Divisibility by 3, 9 and 11 . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.2 Universal Divisibility Test . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.3 Divisibility by power of 2 and 5 . . . . . . . . . . . . . . . . . . . . . . 12

6 Chapter 3: Fermat's Little Theorem 13

7 Chapter 4: Primality Testing 14 7.1 Primality testing using Fermat's Little Theorem . . . . . . . . . . . . . 15 7.2 Primes is in P - The AKS Test . . . . . . . . . . . . . . . . . . . . . . 16

1 Introduction

Number theory is a branch of pure mathematics, which discovers and proves the relationships between diï¬erent sorts of numbers, and the properties of them. In num- ber theory, positive integers attach majority attention from mathematicians. More precisely,