NUMBER  THEORY 

FERMAT'S LITTLE THEOREM 

Fermat's Little Theorem, in number theory, states that if p is a prime number, then for any integer a, the number a raised to the power of p is congruent to a modulo p 

  ap ≡ a (mod p) 

Equivalently,if ''p'" is a prime number and ''a" is an integer not divisble by p then a raised to the power p-1 is congruent to 1 modulo p

ap-1 ≡ 1(mod p)

WILSON'S THEOREM 

Wilson's Theorem states that a natural number n>1 is a prime number if and only if (n-1)! is congruent to -1 modulo n 

 (n-1)! ≡ -1 (mod n)

 (n-1)! ≡ (n-1) (mod n)

In simpler terms, if you calculate the factorial of (n-1) and then divide it by n , the remainder will be n-1 is and only if n is a prime number
EXAMPLE : For the prime number 7 , (7-1)! = 6! = 720 . Dividing 720 by 7 gives remainder 6 which is 7-1.
                    For the composite number 8 , (8-1)! = 7! = 5040 . Dividing 5040 by 8 gives remainder of 0 not                       (8-1) 

MODULAR ARITHMETIC

If A and B are two integers, and A is divided by B, then the relationship

 A = B x Q + R 

is written in modulararithmetic as

A≡ R (mod B)

PROPERTIES OF MODULUS

Let a,b,r,s be integers such that for a given integer n we have a≡r (mod n) and b≡s (mod n). Then

1. a+ b≡r+ s (mod n)

2. ab≡rs (mod n)

3. if a≡b (mod n), then ka≡kb (mod n) for any integer k

4. ka ≡kb (mod n) implies a ≡b (mod n) if and only if gcd(k,n) = 1

5.Let f be a polynomial with integer coefficients.  a−b |f(a)−f(b) for any integers             a,b. This is the same as saying f(a+ d) ≡f(a) (mod d).

6.a≡b (mod n) = ⇒ a+ c≡b+ c, ac≡bc, ac ≡bc (mod n).

INVERSES

 Let p be a prime and a be an integer coprime to p. Then there always exists an integer x such that 

ax≡1 (mod p)

This integer x is called the inverse of a

Example. The inverse of 3 mod 4 is 3 because 3·3 = 9 ≡1 (mod 4).
The inverse of 3 mod 5 is 2 because 3·2 = 6 ≡1 (mod 5).

THEOREM 1 : Let a and m be relatively prime positive integers. Let

the set of positive integers relatively prime to m and less than m be R=

{a1,a2,···,aφ(m)}. S= {aa1,aa2,aa3,···,aaφ(m)}is the same as

R when reduced mod m.

THEOREM 2 : When gcd(a,m) = 1, a always has a distinct inverse mod m.

COROLLARY :The equation ax≡b (mod m) always has a solution when gcd(a,m) = 1.

BONUS QUESTION : Let m and n be positive integers posessing the following property: 

the equation   gcd(11k−1,m) = gcd(11k−1,n)

holds for all positive integers k. Prove that m= (11^r) n for some integer r.

DIOPHANTINE EQUATIONS 

For a polynomial with integral coefficients of multi-variables f(x1, . . . , xn), the problem for finding integer solutions (x1, . . . , xn) of the equation f(x1, . . . , xn) = 0 is called the Diophantine problem, and the equation f(x1, . . . , xn) = 0 is called the Diophantine equation. 

the Diophantine problem is also called the problem for finding integer solutions of equations. 

this TOPIC is confined to linear equations and the systems of linear equations. 

The simplest and typical equation is 

ax + by = c

where a, b, c are constant integers. 

Theorem I. The equation  ax + by = c  has no integer solution if gcd(a , b) ∤c  

Proof.  

 Let d = gcd⁡(a,b)

Then, by definition, there exist integers m,n such that:

                                                                                                                                                                                         d = am+bn

Suppose ax+by=c has an integer solution (x,y) ∈ Z

Then c=ax+by , so: 

d∣(ax+by)=c.

Therefore, d ∣ c   

This proves that a necessary condition for the equation ax+by=c to have integer solutions is that gcd⁡(a,b)∣c.

Hence, if gcd⁡(a,b)∤c , the equation has no integer solutions.

Q.E.D.

Theorem II. When (a , b) = 1, the equation (23.1) always has at least one integer solution. 

Proof.  

Since gcd⁡(a,b)=1, by Bézout’s Identity, there exist integers x0,y0, such that:

ax0+by0=1.

Multiplying both sides by c, we get:

a(cx0)+b(cy0)=c.a(cx_0) 

Thus, x=cx0 ​, y=cy0 is an integer solution to ax+by=c

Q.E.D.

Theorem III. If x0 , y0 is a special integer solution of the Equation ( ax + by = c ), then the general solution                       of it is given by

                               x = x0 + bt 

                               y = y0 − at

                                ∀t ∈ Z 

Proof:

Let (x,y)(x, y)(x,y) be any solution of ax + by =c  different from (x0,y0)

 Then:

ax+by=c                                                                       ( 1 )

ax0+by0=c                                                                   ( 2 )

Subtracting ( 1 ) from ( 2 ), we get:

a(x−x0)+b(y−y0)=0

⇒a(x−x0)=−b(y−y0)

Rewriting:

(x−x0)/b=(y0−y)/a

Let this common value be  t∈Z

x − x0 = bt ,                                                                y − y0 = −at

⇒x = x0 + bt,                                                              y = y0 − at

To justify that t is an integer:
Note that the equation a(x−x0)=−b(y−y0)

• b∣a(x−x0)b , and since gcd⁡(a,b)divides both a and b, this implies b∣(x−x0)
  
  

• Similarly, a∣b(y−y0)⇒a∣(y−y0)
  
  

Thus, both x−x0/b​​ and y0−y/ a are integers, so t∈Z