User:Kosniaz/Kosmas's Notes On Number Theory

Number Theory 101

Modulo N relation

We say that a and b are congruent modulo N (ισότιμοι modulo N), $a=b(modN)$, if N divides a-b.

Modulo N operation

We define mod N, the modulo N operation on an integer a. It returns the smallest non-negative value congruent to a modulo N.

${\displaystyle }$

Primes

P is called a prime iff

• its divisors are itself and 1.
• Its factorization gives us only one non-unit factor

Our working set

We define the set $Z/NZ$ or $Z_{N}$ as the set of remainders modulo N. Equivalently: $Z/NZ=\{0,1,2,...,N-1\}$

Groups, Rings,Fields

A Group is a set with an operation that

• is closed
• has an identity (ουδέτερο στοιχείο)
• is associative (προσεταιριστική)
• every element has an inverse (αντίστροφο)

Α group which is alse commutative (αντιμεταθετικός) is called an Abelian Group. Most of the groups we will encounter are abelian.

A Cyclic Abelian Group is an abelian group that has a generator element, from which we can generate every other element by use of the inverse function or repeated application of the group operation. If for example the group operation is multiplication for each element we have $a=g^{k}$ for some k smaller than the *order* of the group, where order of the group is |S|.

A Ring is a set with two operations, usually denoted + and *, both of which are closed, have an identity element in said set, are associative. Also the '+' operation must be commutative and there must be a '+'-inverse for each element, and also the distrubitive law (επιμεριστική ιδιότητα) must hold. Also, a Commutative Ring is a ring in which multiplication is commutative.

A Field is like a ring, with an added condition: (G/{0}) forms a group with multiplacation.

Inversion modulo P

Consider the following equation:

$ax=1(modN)$

The solution here is the inverse of a modulo N. Such number exists 'iff gcd(a,N) = 1, i.e. iff a and N are coprimes.

Multiplicative Groups

The set of units $U(Z_{m})$

We define $U(Z_{m})$ as the set of all numbers coprime to m in $Z_{m}$. We also call these number units of $Zm$. It is a multiplicative group. Of course, the order of this group is equal to $\Phi (m)$ by definition.

We define the order of an element of a multiplictive group as the least number of times we need to multiply it with itself to get the multiplicative identity,usually denoted $e$. Consider that the generator in a cyclic group has order equal to the order of the group.

Lagrange's Theorem, Euler's Theorem, Fermat's Little Theorem

• Lagrange's Theorem: for each element a in a group of order |G|, $a^{|G|}=e$.
• Lagrange's Theorem (/w Cosets) : if H is a subgroup of G, $|G|=|G/H|*|H|$.
• An important result from Lagrange's Theorem: for each subgroup of G, |H| | |G|.
• Also from Lagrange : for all a in G, the $ord(a)$ divides $|G|$ .
• Euler's Theorem: for $a$ coprime to $n$, $a^{\Phi (n)}=1(modn)$.
• Fermat's Little Theorem: if p is prime, and p does not divide $a$, then $a^{p}=p(modp)$.

The special case: $Z_{p}^{*}$

Continuing from page 51 in the slides..

Basics

Integer division

for each pair of integers a,b, where b is positive, there exists a unique pair of integers q,r so that: $q=qb+r,0\leq r<b$

GCD

$gcd(a,b)=min\{xa+yb|x,y\epsilon Z,xa+yb\geq 0\}$

Chinese Remainder Theorem

Can be used to find the solution of a system of equations of a particular type(more on that later).