1. Modulo arithmetic

Def.: a = b mod n <=> there exists such integer k that a-b = kn

We say "a is congruent to b modulo n"; n is the modulus; b is the residuo;

Theorems about modulo arithmetic:
a=b and b=c => a+c=b+d
a=b and b=c => ac=bd
a=b => a^s=b^s (proof by induction)

Lagrange Theorem:
x=y => P(x)=P(y)

What implies from Lagrange theorem:
* 61345 number we can write down like:
61345 = 6*10^4 + 1*10^3 + 3*10^2 + 4*10 + 5
* we can also represent the number in different base, in any base, let's say base "B":
61345(B) = 6*B^4 + 1*B^3 + 3*B^2 + 4*B + 5 = P(B)
* we can treat this as polynomial P(B); We know that for B=10 it gives the number 61345;

Suppose we want to know what is 61345 congruent to in modulo 9 arithmetic. Because 10=1 mod 9, then what is 61345=P(10) congruent is equal to what is P(1) congruent. Let's put B=1:

P(1) = 6 + 1 + 3 + 4 + 5 = 1 mod 9

So 61345 is congruent to 1 mod 9. We notice that it is enough to add all digits in a number and divide it mod 9 to find out what the number is congruent to modulo 9.

* but it is different with different n.

* also thanks to that theorem we can prove incorrectness of high precision arithmetic calculations.

Proof of Lagrange theorem: by induction on the degree of polynomial
p(x) = a_n*x^n + a_n-1*x^(n-1) + ... + a_1*x + a_0
- for n = 0:
p(x) = a_0 = a_0 mod n = p(y) mod n
- for n = k:
p(x) = a_k*x^k + a_k-1*x^(k-1) + ... + a_1*x + a_0
p(y) = a_k*y^k + a_k-1*y^(k-1) + ... + a_1*y + a_0

we notice that x^k+1 = y^k+1 mod n (Th3), and even that a_k+1*x^k+1 = a_k+1*y^k+1 mod n (Th2 + reflexivity). Adding these terms to both equations we get the case for n=k+1.

Partition Theorem: - ????


2. Group (G,+)

1. is closed (x+y belongs to G)
2. is associative (x+(y+z)=(x+y)+z)
3. has additive identity element (x+e=x)
4. for each element has corresponding additive inverse element (x+y = e = y+x)
* if it also has commutivity property (x+y=y+x), it is called an Abelian group

In modulo n arithmetics the numbers 0-(n-1) are called class representatives. In one class there will be all numbers congruent to class representative mod n.

3. Relations

Def.: relation is a subset of Cartesian product.

Congruence is in fact a relation. It is an equivalence relation:
1. it's symmetric
2. it's transitive
3. it's reflexive

4. Chinese Remainder Theorem

Given a series of n coprime integers mi such that
M = /\m_i = m_1 * m_2 * ... * m_n
and an integer x such that
x = r_i mod m_i, for all 1<=i<= n
then there's only one integer y in the range 0<= x<M-1, where y = x mod m_i
Proof: let's assume x=r_i mod m_i and y=r_i mod m_i; then
x=y mod m_i
, and this by definition equals
x-y=k_i*m_i, for all i
because m_i are coprime, and x-y is a divisor of both k_i and m_i, it means x-y is a divisor of M.
x-y=kM
the only k which makes x-y be in range 0 to M-1 is k=0:
x-y=0 => x=y
Contradiction.

5. Function

Is a relation where first element of ordered pair can appear in 1 ordered pair.

Def.: Function is ordered triple of sets (X,Y,F), X-domain, Y-codomain, F-function range, where F={(x,y)|x belongs to X, y belongs to Y} and each x is the 1st element in only one pair.

6. CRT notation

The notation: x=(1,2,4)_(3,4,5) is equal to set of equations:

x = 1 mod 3 n
x = 2 mod 4
x = 4 mod 5

This defines x unambigiously in interval 0 to 3*4*5-1.

7. Euclidean algorithm

a/b = k+r/b <=><=> a = b*k + r

Euclidean algorithm uses the fact that gcd(a,b) = gcd(b,r). Why is that fact true?

Proof: let's denote:
(1) gcd(a,b) = s(2) gcd(b,r) = t

a) a=l*s, as s divides a (1)
b=w*s, as s divides b (1)

If we divided a/b we would get:

a = b*k + r
=> l*s = k*w*s + r
=> l*s - k*w*s = r
=> s*(l - k*w) = r
=> r is a multiple of s

but gcd(b,r) = t, so s<=t b) b=d*t, as t divides b (2)
r=e*t, as t divides r (2)

If we divided a/b we would get:

a = b*k + r
=> a = d*t*k + e*t
=> t*(d*k + e) = a
=> t divides a and b = > s>=t

a) and b) => t = s .

* CRT multiplication is LINEAR with respect to number of digits of multiplied numbers!

8. Finding inverse in modulo n arithmetic

For inverse of x=1/m we want to find such y, that m*y = 1 mod n.

How to do it in other way than guessing (gcd(m,n) = 1):

n= k_1*m + r_1
m = k_2*f + r_2
f = ...
(...)
d = 1*z + 0

then:
r_1 = k_1*m - nr_2 = k_2*f - m
(...)
0 = 1*z - d

ahhh, just check wiki

... until we get 1 = r*m-q*n => r*x = 1 mod n => r is inverse to x

Want to leave a comment? Visit this post's issue page on GitHub and just post your comment as the issue's comment (you'll need a GitHub account. What? Like you don't have one yet?!).