Elementary Number Theory and its applications

Essay by bsw910715University, Bachelor'sA, September 2014

download word file, 35 pages 0.0

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 different sorts of numbers, and the properties of them. In num- ber theory, positive integers attach majority attention from mathematicians. More precisely,