Blog Archives

Modular Arithmetic


Modular arithmetic is a notation and set of mathematics that were first introduced by¬†Carl Friedrich Gauss. ūüôā

The major insight is that equations can fruitfully be analyzed from the perspective of remainders. Standard equations use the ‘=’ sign. Modular arithmetic uses the ‘‚Č°‘ sign. Two values that are ‘‚Č°’ to each other are said to be¬†congruent¬†relative the¬†modulus. In the case below, the¬†modulus¬†is 3. ¬†ūüôā

Here’s an example of a modular equation:

7 ‚Č° 1 (mod 3).

By definition, this means that 3 divides 7 Р1.

Definition 1: a ‚Č° b (mod c) if and only if c divides a – b.

This definition tells us the following is true:

7 ‚Č° 1 ‚Č° 10 ‚Č° -2 (mod 3).

Now, one of the most interesting things about ‘‚Č°’ is that it follows many of the same relations as ‘=’ . ¬†ūüôā ūüôā

Notice 1: For any value a,b,c,d,n where a ‚Č° b (mod n) and c ‚Č° d (mod n): ¬†ūüôā

(a)¬†a + c ‚Č° b + d (mod n)
 Proof :  We know that n divides (a + c) Р(b + d) since this is equal to: (a -b) + (c Рd).

(b)¬†a – c ‚Č° b – d (mod n)
Proof : We know that n divides (a Рc) Р(b Рd) since this is equal to: (a Рb) Р(c Рd).

(c)¬†ac ‚Č° bd (mod n)
Proof : We know that n divides ac Рbd since this is equal to : c(a Рb) + b(c Рd).

(Q.E.D) 

Notice ¬†2: If a ‚Č° b (mod n) then:

(a)¬†a + c ‚Č° b + c (mod n)
Proof : We know (a) since n divides a + c Р(b + c) = a Рb.

(b)¬†a – c ‚Č° b – c (mod n)
 Proof : We know (b) since n divides a Рc Р(b Рc) = a Рb.

(c)¬†ac ‚Č° bc (mod n)
Proof: We know (c) since n divides ac Рbc = c(a Рb)

(Q.E.D)

Corrolary 2.1: a ‚Č° d (mod n), b ‚Č° e (mod n), c ‚Č° f (mod n), then:
a + b + c ‚Č° d + e + f ¬†mod n¬†

(1) We know that¬†a + b ‚Č° d + e¬†from above.
(2) We therefore know that¬†(a + b) + c ‚Č° (d + e) + f.

(Q.E.D)

Notice ¬†3: a + b + c ‚Č° 0, a ‚Č° 0 (mod p), then b + c ‚Č° 0 (mod p).

(1)¬†a + b + c ‚Č° 0 (mod p)¬†[Definition of¬†‚Č°¬†]

(2)¬†b ‚Č° c (mod p) ‚Üí a + b ‚Č° a + c (mod p)¬†[See above]

(3) So,¬†0 ‚Č° a + b + c ‚Č° 0 + b + c ‚Č° b + c (mod p).

(Q.E.D)

I will cover modular arithmetic in depth ūüôā ūüôā
Today you must we wondering about its application ..
But after whole course You will surely love this topic
Thank you ūüôā ūüôā

If any doubts , then dont hesitate in asking Your doubts ūüôā ūüôā
I will surely love to solve your doubts

Fundamental Theorem Of Arithmetic


Before, we can provide this theorem, we will need an initial theorem on division and one lemma which will we borrow from Euclid.

Theorem 1: Division Algorithm for Integers

This theorem shows that given any two integers, there exist a unique divisor and a unique remainder.

(1) Let¬†S¬†be a set such that¬†{ a – bc : c¬†is an¬†integer¬†and¬†a-bc ‚Č• 0}

(2) S is not empty.

Case I: b divides a

In this case, then there exists a c where a Рbc = 0. Therefore, 0 is an element of this set.

Case II:¬†b¬†doesn’t divide¬†a

In this case, there exists an c where a Рbc has a remainder is greater than 0. This remainder is then an element of this set.

(3) Then, then there exists d such that d is the smallest element of the set. [Well Ordering Principle]

(4) We know that d is less than b.

(a) Assume that d is greater than or equal to b.

(b) Then d Рb is greater than or equal to 0.

(c) Since

d – b = (a – bc) – b = a – bc – b = a – b(c+1)

(d) We conclude that a Рb(c+1) must be an element of S.

(e) But a Рb(c+1) is less than d

(f) Which is a contradiction since d is the smallest element from step #3.

(5) Finally, for any a,b, the lowest value d and the remainder c are unique.

(a) Assume C,D are integers that can be derived from a,b.

a = bc + d, d is greater than 0 and less than b.
a = bC + D, D is greater than 0 and less than b.

(b) So

bc + d = bC + D –> b(c – C) = d – D

(c) Which means that b divides (d РD).

(d) Since d РD is less than b, we know d РD = 0 and that d = D.

(e) Which gives us b(c РC) = 0 or that c РC = 0.

(f) We can therefore conclude that c = C.

QED

Lemma 2: Euclid’s Lemma

This lemma shows that given a prime that divides a product, either it divides one value or it divides the other.

(1) Let’s assume a prime¬†p¬†divides a product¬†ab.

(2) Let’s assume that¬†p¬†does not divide¬†a.

(3) Then gcd(p,a)=1. [See blog on Greatest Common Denominators for details]

(4) There exists s,t such that 1 = as + pt. [See blog on Greatest Common Denominators]

(5) Multiplying both sides with b gives us:

b(1) = b(as + pt) = b = abs + ptb

(6) Since p divides ab, there exists k such that ab = pk.

(7) Combining with (5), we get

b = pks + ptd = p(ks + td).

QED

We can also tag on a corollary.

Corollary 2.1: Generalized Euclid’s Lemma

The idea here is that if a prime divides a product of n elements, then it is necessarily divides at least one of those elements.

(1) Let’s assume that we have a product of¬†n¬†elements.

a = a1¬†* a2¬†* … * an

(2) We can take any one of these elements and get:

a = a1¬†* (a2¬†* … * an)

(3)So, by Euclid’s Lemma (see Lemma 2 above), the prime either divides¬†a1¬†or one of the rest of the elements.

(4) So, either it divides a1 or a2 etc.

(5) And we get to the last two elements, we are done by Euclid’s Lemma.

QED

Theorem 3: Fundamental Theorem of Arithmetic

This theorem proves that each integer greater than 1 is the product of a unique set of primes.

(1) Let S be a set S of {primes or products of primes > 1}.

(2) 2 is an element of S since 2 is prime.

(3) From (1), (2) there exists a value n which is 3 or greater where all values less than n and greater or equal to 2 are in S.

(4) If n is a prime, then it is a member of S.

(5) If n is not a prime, then it is also a member of S.

(a) If n is not a prime, then there exist a,b such that n=ab where a,b are greater than 1 and less than n. [Definition of a prime]

(b) But a,b must be elements of S since they are less than n. [From step #3 above]

(c) Then, n must also be a member of S since n is a product of two numbers which are either primes or products of primes.

(6) Now, all the primes that make up n are necessarily unique.

(a) Let¬†n = p1¬†* p2¬†* … pr¬†= q1¬†* q2¬†* … qs¬†where p,q are all primes.

(b) Let’s start with¬†p1

(c) Either¬†p1¬†divides¬†q1¬†or¬†q2¬†or someother value. [see Euclid’s Generalized Lemma above]

(d) Likewise, each value pr can be matched by some value qs.

(e) In other words, they must necessarily be the same combination.

QED

CoPrime Numbers : x^n + y^n = z^n


This post is about the equation:
xn + yn= zn

I will show that given any three integers that satisfy this equation, either:

(a) all three of them are coprime with each other

or                                         

(b) it is possible to cancel out common components and derive three numbers that are coprime.

Two numbers are coprime if they do not share any common divisors.

Definition 1: Coprime

Two numbers x,y are said to be coprime if and only if d divides x, d divides y -> d = 1

Two numbers x,y are said to not be coprime if and only if there exists a value d > 1such that d divides x, d divides y

Now, here’s the proof that was promised:

Lemma: We can reduce any solution to xn + yn = zn to a form where x,y,z are coprime.

To prove this, we will need to prove two things:

(1) If a factor divides any two values of this equation, then the n-power of it divides the n-power of the third value.

(2) If an n-power of a factor divides the n-power of a value, then the factor divides the value itself.

Step 1: For xn + yn = zn, the n-power of any common factor of two divides the n-power of the third.

Case I: Let’s assume d divides x, d divides y

(1) There exists x’, y’ such that: x = d(x’), y = d(y’)
(2) zn¬†= xn¬†+ yn¬†= (dx’)n¬†+ (dy’)n
= dn(x’)n¬†+ dn(y’)n
= dn[(x’)n¬†+ (y’)n]

Case II: Let’s assume d divides z and d divides x or d divides y

(1) Let’s assume d divides x (the same argument will work for y)
(2) There exists x’, z’ such that: x = d(x’), z = d(z’)
(3) We now say yn = zn Рxn
(4) We can now follow the same reasoning as above.

QED

Step 2: dn divides xn → d divides x

(1) Let c be the greatest common denominator (gcd) for d,x.
(2) Let D = d / c, X = x / c.
(3) Now the gcd of (X,D) = 1. [See here for the explanation]
(4) So, the gcd of (Xn,Dn) = 1.
(5) We know that there exists k such that xn = k * dn [Since dn divides xn ]
(6) Applying (2), we get (cX)n = k*(cD)n
(7) Which gives us: cnXn = k * cnDn
(8) Dividing cn from each side gives: Xn = Dn*k
(9) Now it follows that gcd(Dn,k) = 1.

(a) Assume gcd(Dn,k) = a, a > 1
(b) Then, a divides Dn and Xn [From 8]
(c) But¬†gcd(Dn,Xn) ‚Ȇ 1.
(d) But this contradicts (4)
(e) So, we reject our assumption.

(10) So, we can conclude that k is an n-power. [See blog on Infinite Descent for the proof]
(11) Which means that there exists u such that un = k.
(12) And we get Dn * un = Xn
(13) And (Du)n = Xn
(14) Implying that Du = X and multiplying by c that du=x.
(15) Which proves that d divides x.

QED