**1. Elementary Number Theory **

** 1.1. Arithmetic Tables **

Generating addition tables modulo

Example:

forms a *group* under addition (,+).

For a set with a defined operation, the Group axioms are: Closure and existence of identity and inverse. is a subset of (all elements multiplied by n). The subset is a subgroup: closed under addition, associative; additive inverse, and identity belong to . The group of integers modulo denoted also form a group under addition.

Monoids exclude the requirement of the existence of inverse, so is a submonoid of . A coset of a subgroup is a translation of the subgroup by an element of the group. The subsets , i.e all the residue classes modulo are cosets of the subgroup

Multiplication table *modulo*

C++ code

#include<iostream.h> #include<stdio.h> #include<math.h> void addition_table() { int k,a; cout<<"Enter X to generate (Z_X,+)"<<endl; cin>>k; cout<<"\n"; for(int i=0;i<k;i++) { cout<<endl; for(int j=0;j<k;j++) { a=(i+j)%k; // a=(i*j)%k; for multiplication table cout<<a<<'\t'; } } }

** 1.2. Division Algorithm **

Given two inputs, any integer and a positive integer it is needed to find two integers and such that . It is clear that if then and . If then the formal proof follows from the well-rdering principle (every nonempty set in ) has a least element by constructing the set SInce we’ve constrained k and it is non empty therefore it must have a least element which we call . In other words, we choose such that is the smallest possiple positive integer (or zero). So

The Euclidean algorithm to find the gcd of two numbers is a consequence of the fact that , then gcd gcd. As then all common divisors of and are also divisors of , i.e . Also, as and so . Two positive integers that divide each other are equal.

Following is an implementation of the Euclidean Algorithm. Negative integeres would cause it to go in an infinite loop so I’ve added some lines.

include<iostream.h> int euclidean(int a, int b) { int a,b; a = a>0 ? a : -a; b = b>0 ? b : -b; do{ a = a>b && a!=b ? a-b : a; b = b>a && b!=a ? b-a : b; cout<<"{"<<a<<","<<b<<"}->"; }while(a!=b); cout<<"\n GCD="<<a<<endl; }

Output

root [5] euclidean(343423,6268768)

{343423,5925345}->{343423,5581922}->{343423,5238499}->{343423,4895076}->{343423,4551653}-> {343423,4208230}->{343423,3864807}->{343423,3521384}->{343423,3177961}->{343423,2834538}-> {343423,2491115}->{343423,2147692}->{343423,1804269}->{343423,1460846}->{343423,1117423}-> {343423,774000}->{343423,430577}->{343423,87154}->{256269,87154}->{169115,87154}-> {81961,5193}->{76768,5193}->{71575,5193}->{66382,5193}->{61189,5193}->{55996,5193}-> {50803,5193}->{45610,5193}->{40417,5193}->{35224,5193}->{30031,5193}->{24838,5193}-> {19645,5193}->{14452,5193}->{9259,5193}->{4066,1127}->{2939,1127}->{1812,1127}-> {685,442}->{243,199}->{44,155}->{44,111}->{44,67}->{44,23}->{21,2}->{19,2}->{17,2}-> {15,2}->{13,2}->{11,2}->{9,2}->{7,2}->{5,2}->{3,2}->{1,1}-> GCD=1

The GCD of two numbers is also their smallest integral linear combination.

This is fairly straighforward. Consider , i.e and so As is the greatest number which can divide the expression, i.e leave an integer, for arbitrary the above property follows.

More formally, it can be proved using the well ordering principle. Consider the set of all positive integers By the well ordering principle has a least element . Any common divisor and is also a divisor of . It would be sufficient to show that also divides and . Let the remainder on dividing be , i.e

But then

Which cannot be as is the least element and hence

The set of numbers form a subgroup of . It staisfies all the group axioms. From the above I know that has a least element, gcd. Every multiple of is , as . Since and therefore divides all elements of , i.e every member of is a multiple of this number. The subgroup of that is generated by non zero integers and is generated by the single number . (If any number in the subgroup such that and for then must be in the subgroup by defintiion, but is lesser than arriving at a contradiction.) \linebreak

**Example**: we know that has integer solutions, while for example, has none. If and then . As must be even, we can write and . Take one pair of solutions, and the other solutions have the form and . There are others possible. \linebreak

**Example:** All consecutive fibbonaci numbers are coprime. Thus, their gcd is . Proved. \linebreak

In general, the subgroup is a cyclic group generated by the single element gcd

** 1.3. Generating number system using the division algorithm **

Theorem 1Let Then every positive integer can be expressed uniquely in the form where and

*Proof:*Any number can be written as

with and

As and all ‘s are positive integers, this sequence will terminate. On substituting

It can be easily be proved that this is unique.

** 1.4. Continued Fractions from the division algorithm**

** 1.5. Prime Factorization **

Fundamental theorem of arithemtic: every integer greater than can be expressed as product of powers of primes. This factorization is unique up to a permutation.

If a number is composite, atleast on of its prime factors is For example any composite number less than 101 would have either 2,3 or 5 as one of its prime factors. This considerably reduces the number of operations in a brute force method to find primes called the Sieve of Eratosthenes.

See: *Primality Testing*

**1.6. Congruences and Modular Arithmetic**

** 1.7. Well Ordering Principle and induction **

To be honest, I am still of doubt that the formal process of writing proofs might not be as fruitful for me. It requires me to lose a bit of my intuition and then regain it with a solid understanding of the underlying machinery. With a bit of scepticism, this is a section on the very basics.

\texbf{Well Ordering Principle} \fbox{Every non empty set of positive integers has a least element}

There is no positive integer between and . Suppose is a nonempty set, so by the well ordering principle it should have a least element. Let be the least element, but then so we arrive at a contradiction.

There is no positive integer between and . Let then implying there is an integer between and .

An extension of the WOP to non negative integers can be made using “proof by cases”.