# 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.

(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 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 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 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.