Baby Steps: The Basics

1. Elementary Number Theory

1.1. Arithmetic Tables

Generating addition tables modulo ${n}$

Example: ${(\mathbb{Z}_7,+)}$

$\displaystyle \begin{array}{c c c c c c c} 0 & 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 2 & 3 & 4 & 5 & 6 & 0\\ 2 & 3 & 4 & 5 & 6 & 0 & 1 \\ 3 & 4 & 5 & 6 & 0 & 1 & 2 \\ 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ 5 & 6 & 0 & 1 & 2 & 3 & 4\\ 6 & 0 & 1 & 2 & 3 & 4 & 5\\\end{array}$

${\mathbb{Z}}$ forms a group under addition (${\mathbb{Z}}$,+).

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

Monoids exclude the requirement of the existence of inverse, so ${\mathbb{N}}$ is a submonoid of ${\mathbb{Z}}$. A coset of a subgroup is a translation of the subgroup by an element of the group. The subsets ${\{n\mathbb{Z}+1,\cdots,n\mathbb{Z}+(n-1)\}}$, i.e all the residue classes modulo $n$ are cosets of the subgroup ${n\mathbb{Z}}$

Multiplication table modulo${7}$

$\displaystyle [\begin{array}{c c c c c c c} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 4 & 5 & 6\\ 0 & 2 & 4 & 6 & 1 & 3 & 5\\ 0 & 3 & 6 & 2 & 5 & 1 & 4\\ 0 & 4 & 1 & 5 & 2 & 6 & 3\\ 0 & 5 & 3 & 1 & 6 & 4 & 2 \\ 0 & 6 & 5 & 4 & 3 & 2 & 1\end{array}$

C++ code

#include&lt;iostream.h&gt;
#include&lt;stdio.h&gt;
#include&lt;math.h&gt;

{
int k,a;
cout&lt;&lt;&quot;Enter X to generate (Z_X,+)&quot;&lt;&lt;endl;
cin&gt;&gt;k; cout&lt;&lt;&quot;\n&quot;;
for(int i=0;i&lt;k;i++)
{
cout&lt;&lt;endl;

for(int j=0;j&lt;k;j++)
{
a=(i+j)%k; // a=(i*j)%k; for multiplication table
cout&lt;&lt;a&lt;&lt;'\t';
}
}

}


1.2. Division Algorithm

Given two inputs, any integer ${a}$ and a positive integer ${b}$ it is needed to find two integers ${q}$ and ${0\leq r< b}$ such that ${a = bq+r}$. It is clear that if ${b>a}$ then ${q=0}$ and ${r=a}$. If ${b then the formal proof follows from the well-rdering principle (every nonempty set in ${\mathbb{N}}$) has a least element by constructing the set ${k=\{ a-bq: k\in\mathbb{N}\}}$ SInce we’ve constrained k and it is non empty therefore it must have a least element which we call ${r}$. In other words, we choose ${q}$ such that ${a-bq}$ is the smallest possiple positive integer (or zero). So

$\displaystyle a-b(q+1)<0\leq a-bq$

$\displaystyle \Rightarrow 0\leq r=a-bq

The Euclidean algorithm to find the gcd of two numbers is a consequence of the fact that ${b = aq+r}$, then ${d=}$ gcd${(a,b)=}$ gcd${(a,r)}$. As ${r = b-aq}$ then all common divisors of ${a}$ and ${b}$ are also divisors of ${r}$, i.e ${r|d}$. Also, as ${d|b}$ and ${b = aq+r}$ so ${d|r}$. 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&lt;iostream.h&gt;

int euclidean(int a, int b)
{
int a,b;
a = a&gt;0 ? a : -a;
b = b&gt;0 ? b : -b;
do{
a = a&gt;b &amp;&amp; a!=b ? a-b : a;
b = b&gt;a &amp;&amp; b!=a ? b-a : b;
cout&lt;&lt;&quot;{&quot;&lt;&lt;a&lt;&lt;&quot;,&quot;&lt;&lt;b&lt;&lt;&quot;}-&gt;&quot;;
}while(a!=b);
cout&lt;&lt;&quot;\n GCD=&quot;&lt;&lt;a&lt;&lt;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 ${3=gcd(57,36)}$, i.e ${3|57}$ and ${3|36}$ so ${3|57x+36y}$ As ${3}$ is the greatest number which can divide the expression, i.e leave an integer, for arbitrary ${x,y\in\mathbb{Z}}$ the above property follows.

More formally, it can be proved using the well ordering principle. Consider the set of all positive integers ${D=\{ ax+by:ax+by>0 \}}$ By the well ordering principle ${D}$ has a least element ${d}$. Any common divisor ${a}$ and ${b}$ is also a divisor of ${d}$. It would be sufficient to show that ${d}$ also divides ${a}$ and ${b}$. Let the remainder on dividing ${a}$ be ${r}$, i.e

$\displaystyle a = dq+r \; ; 0\leq r

But then

$\displaystyle r = a(1-qx) + b(-qy) \; \mbox{i.e} \; r\in D$

Which cannot be as ${d}$ is the least element and hence ${r=0}$

The set of numbers ${S =\{ ax+by|x,y\in \mathbb{Z}\} }$ form a subgroup of ${(\mathbb{Z},+)}$. It staisfies all the group axioms. From the above I know that ${S}$ has a least element, ${d=}$gcd${(a,b)}$. Every multiple of ${d}$ is ${S}$, as ${nd = a(nx)+b(ny)}$ ${\forall n\in Z}$. Since ${d|a}$ and ${d|b}$ therefore ${d}$ divides all elements of ${S}$, i.e every member of ${S}$ is a multiple of this number. The subgroup ${S}$ of ${(\mathbb{Z},+)}$ that is generated by non zero integers ${a}$ and ${b}$ is generated by the single number ${d}$. (If any number ${c}$ in the subgroup such that ${c\neq dq}$ and ${c=dq+r}$ for ${0\leq r then ${r = c-dq}$ must be in the subgroup by defintiion, but is lesser than ${d}$ arriving at a contradiction.) \linebreak

Example: we know that ${2x+3y = 1}$ has integer solutions, while for example, ${2x+3y=0}$ has none. If ${2a+3b=1}$ and ${2c+3d = 1}$ then ${2(a-c) = 3(d-b)}$. As ${d-b}$ must be even, we can write ${a=c+3t}$ and ${b=d-2t}$. Take one pair of solutions, ${c=5}$ and ${d=-3}$ the other solutions have the form ${x=5+3t}$ and ${y =-3-2t }$. There are others possible. \linebreak

Example: All consecutive fibbonaci numbers are coprime. ${gcd(a_{n+1},a_n) = gcd(a_{n+1}-a_n,a_n) = gcd(a_{n-1},a_n)=\cdots gcd(1,1)}$ Thus, their gcd is ${1}$. Proved. \linebreak

In general, the subgroup ${\{ax+by+cz+\cdots | x,y,z\cdots \in \mathbb{Z}\}}$ is a cyclic group generated by the single element gcd${(a,b,c,\cdots)}$

1.3. Generating number system using the division algorithm

Theorem 1 Let ${b\geq 2,\in\mathbb{Z}}$ Then every positive integer ${N}$ can be expressed uniquely in the form ${N=a_kb^k+a_{k-1}b^{k-1}+ \cdots +a_1 b+a_0 }$ where ${0\leq a_0,a_1,\cdots,a_k and ${a_k\neq 0}$

Proof:Any number ${N}$ can be written as

$\displaystyle N = q_0 b +a_0$

with ${q\geq 0}$ and ${0\leq a_0

$\displaystyle q_0 = bq_1 +a_1$

$\displaystyle q_1 = bq_2 +a_2$

$\displaystyle \cdots$

$\displaystyle q_{k-1} = 0b + a_{k}$

As ${N>q_0>q_1>\cdots}$ and all ${q}$‘s are positive integers, this sequence will terminate. On substituting

$\displaystyle N=q_0 b +a_0 = ( bq_1 +a_1) b +a_0 =( b(bq_2 +a_2)+a_1) b +a_0$

$\displaystyle = q_{k-1}b^k + a_{k-1}b^{k-1}+\cdots+ a_1b + a_0$

$\displaystyle = a_kb^k + a_{k-1}b^{k-1}+\cdots+ a_1b + a_0$

It can be easily be proved that this is unique. $\Box$

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 $n$ is composite, atleast on of its prime factors is $\leq\lfloor \sqrt{n} \rfloor$ 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.

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 ${0}$ and ${1}$. Suppose ${S=\{n\in\mathbb{Z}|0 is a nonempty set, so by the well ordering principle it should have a least element. Let ${l}$ be the least element, but then ${0 so we arrive at a contradiction.

There is no positive integer between ${a}$ and ${a+1}$. Let ${a then ${0 implying there is an integer between ${0}$ and ${1}$.

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

$\displaystyle \begin{array}{|c| c c c|}\hline & g^{0} & g^{1} & g^{2}\\\hline g^{0} & g^{0} & g^{1} & g^{2}\\ g^{1} & g^{1} & g^{2} & g^{0}\\ g^{2} & g^{2} & g^{0} & g^{1} \\\hline \end{array}$