Section 006) Chinese Remainder Theorem

If m and n are positive integers which are relatively prime i.e. GCD(m , n ) = 1. Then there exists an integer N such that

$N \equiv a (\mod m)$
$N \equiv b (\mod n)$

Moreover $N \equiv x (\mod mn)$ where x is unique.

This can be proved  but I am not specifying the prrof here

This can be generalized to n  integers.

$N \equiv a_i (\mod m_i)$ where i varying from 1 to n and $m_i$ are pairwise relatively co-prime then there exists x such that

$x = \sum_{i=1}^n\frac{a_ib_iM}{m_i}$ where M is product of all $m_i$ and $b_i$ is determined from M as below

$b_i\frac{M}{m_1}  \equiv 1 \mod m_1$

We illustrate the same with an example below

Problem 1

What would be the least positive . which give the remainder 1 when divided by 7,2 when divided by 9 and 11 when divided by 11 

Solution 1

Let the number be x 

We have remainder 1 when divided by 7,2 when and 3 when divided by 11

So

$x=1\pmod 7\cdots(1)$
$x=2\pmod 9\cdots(2)$
$x=3\pmod {11}\cdots(3)$

Now 7 ,9 and 11 are pair wise co-prime 

So M= 7 * 9 * 11 = 693

So $x = 1 a_1b_1 + 2 a_2b_2 + 3 a_3b_3 \pmod {693}$ as M = 693 

Now let us compute $a_1,a_2,a_3$


$a_1 = \frac{M}{7}  = \frac{693}{7} = 99$
$a_2 = \frac{M}{9}  = \frac{693}{9} = 77$
$a_3 = \frac{M}{11}  = \frac{693}{11} = 63$

Now we need to compute $b_1,b_2,b_3$ such that

$99b_1 =1   \pmod 7$ or $b_1 =1  \pmod 7$ or $b_1 = 2$

$77b_2 =1   \pmod 9$ or $5b_2=1   \pmod 9$ or $b_2 = 2$
  
$63b_3 = 1 \pmod {11}$  or $8b_3 =1 \pmod {11}$ so $b_3 = 7$ as $ 7 * 8 = 56 = 1 \pmod {11}$

I have mentioned the above in hit and trial method because the co-coefficients are low and they can be computed using extended euclidean algorithm as below.

Let us try  the $3^{rd}$ part i.e.$8b_3 =1 \pmod {11}$

That is solve  $8x =1 \pmod {11}$

Or $8x= 1 + 11y$ 

We need to  compute $ 1= 8a + 11b$ where b is negative then a is the inverse of 8

To compute a ,b we have

$11 = 1 * 8 + 3$

So $3 = 11 -8$

$8 = 3 * 2 + 2$ or $2 = 8- 3 * 2 = 8- 2 * (11-8) = 3 * 8 - 2 * 11$

$1 = 3 -2 = (11-8) - ( 3 * 8 - 2 * 11) = 3 * 11 - 4 * 8$

We have found $1 = 8a + 11 b$  where $b = 3$ which is positive

We need to convert it to positive

Knowing $8a + 11 b = 8(a+11t) + 11(b-8t)$ identity if we add 8 to b and subtract 11 from a we get

$1 = 8(-4 +11) + 11(3 -8) = 7 * 8 - 5 * 11$

So $8 * 7  =1 \pmod {11}$

Hence 7 is inverse of 8  

So $x = 1 * 99 * 1 + 2 * 77 * 2 + 3 * 63 * 7 \pmod {693} = 1730 \pmod {693}$

$= 344 \pmod {693}$

So x if of the form $693n + 344$  or lowest x = 344


Problem 2

Find all integers that leave a remainder 1 when divided by either 2 or 5 but divisible by 3.

Solution 2

Let the number be x 

We have remainder 1 when divided by 2 or 5 but divisible by 3

So

$x=1\pmod 2\cdots(1)$
$x=1\pmod 5\cdots(2)$

$x=0\pmod 3 \cdots(3)$

we can combine (1) and (2) are remainders are same to have
$x=1\pmod 10 \cdots(4)$

now we need to solve the following

$x=0\pmod 3 \cdots(5)$

$x=1\pmod {10} \cdots(6)$

we shall use CRT as 3 and 10 are coprimes

M = 3 * 10 = 30

$a_1 = \frac{30}{3}  = 10$
$a_2 = \frac{30}{10}  =3$

Now we need to compute $b_1,b_2,b_3$ such that

$10b_1 =1   \pmod 3 $ or $b_1 =1  \pmod 3$ or $b_1 = 1$ (actually we need not compute as coefficient = 0)

$3b_2 =1   \pmod {10} $ or $b_2=7   \pmod {10}$ or $b_2 = 7$

so the number  = $0 * 10 * 1 + 1 *3 * 7 = 21  \pmod{30}$ 
  

Section 005) Pigeonhole Principle

Introduction

Pigeonhole principle simply states that if n+1 pigeons occupy n containers then one container shall have at least 2 pigeons.

As an example if you have socks of 2 colors and you pick 3 socks then at least 2 socks shall be of same color

If there are 13 persons in a room then 2 persons are born in the same month.

We now solve a couple of problems based on Pigeonhole principle

Problem  1

Show that inside  a square of radius 2 if we have 5 points then there are 2 points distance between them is less than $\sqrt{2}$.

Solution 1

Divide the square into 4 squares of size 1. As we have 5 points in 4 squares(edges includes) there are at least 2 points in one square. distance between 2 points inside the square is less than $\sqrt{2}$


Problem  2

 If you pick 51 numbers from the numbers 1 to 100 then there are 2 numbers whose sum is 101.

Solution 2

We can make 50 sets (1,100), (2,99), (3, 98) .... (50,51).

Now if we chose 51 numbers from the above 50 sets then 2 numbers must belong to same  set and and the sum shall be 101.

Section 004) Principle of Mathematical Induction

Introduction 

Principle of Mathematical induction (in short also known as PMI) is a method for proving a
proposition.  This consists of 2 steps the $1^{st}$ step is called the base case (also called basis)
and the $2^{nd}$ step is called induction step.

To prove by mathematical induction we have a hypothesis and then prove the hypothesis. The hypothesis is called induction hypothesis.They are explained below.

Steps  In Principle of Mathematical Induction 

In PMI the 2 steps are
Base step: This is true for some starting value say n. Typically but not always n = 1.
Induction step: Say this is true for all $n <=k$. Then it is true for k+ 1.
Combining the above 2 we prove it by mathematical induction.

There are two principles of mathematical induction

1st Principle of Mathematical Induction

In case the inductive step is based on the last value only then it is the 1st  Principle of
Mathematical Induction.

2nd Principle of Mathematical Induction

If it is based on more than one value then this is called 2nd Principle of Mathematical Induction.
This is also known as Principle of Strong Mathematical Induction as it is based on k and k-1 (or more than one value).

Proof  by Principle of Mathematical Induction

To prove by Principle of Mathematical Induction both the steps need to be proved. In absence of any one the proof is incomplete and hence is invalid.

This is demonstrated below how the proof by induction can be wrong unless applied properly.

To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by
mathematical induction that all horses are of the same color.

Base case: In a set of only one horse, there is only one color.

Inductive step: Assume as induction hypothesis that within any set of n horses, there is only
one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider
the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore
within each there is only one color. But the two sets overlap, so there must be only one color
among all n + 1 horses.

The base case n = 1 is trivial (as any horse is the same color as itself), and the inductive step
is correct in all cases $n > 1$. However, the logic of the inductive step is incorrect for n = 1,
Because the statement that "the two sets overlap" is false (there are only n + 1 = 2 horses prior
to either removal, and after removal the sets of one horse each do not overlap).

Hence the principle of induction has not been applied correctly and hence incorrect conclusion.

Here we provide couple of examples

Problem 1

Using PMI prove that $x^2+3x+3$ is a factor of $(x+1)^{n+1} + (x+2)^{2n-1}$
for integer $n >= 1$

Solution 1

n =1 gives $(x+1)^{n+1} + (x+2)^{2n-1} = (x+1)^2 + (x+2) = x^2 + 2x + 1 + x + 2 = x^2 + 3x + 3$ divisible

So the 1st step that is base step is proved

Let it be true for n = k.

We need to prove for n= k+ 1
Let $f(k) = (x+1)^{k+1} + (x+ 2)^{2k- 1}$
So $f(k+1) = (x+1)^{k+2} + (x+2)^{2k+ 1}$
$= (x+1)(x+1)^k + (x+2)^2 *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x^2+4x + 4) *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x + 1 + x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x + 1)(x+2)^{(2k-1} + (x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1)[(x+1)^k + (x+2)^{2k-1}] + (x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1) f(k) + (x^2+3x + 3) *(x+2)^{2k-1}$

As both terms are divisible by $x^2+3x+3$ so f(k+1) is divisible by $x^2+3x+3$

So step of induction is proved

Hence proved as we have proved both the base step and induction step to be true.

Problem 2

Suppose x is a real number  and $x + \frac{1}{x}$ is an integer
Prove for all $n > 1, x^n + \frac{1}{x^n}$ is an integer.

Solution 2

$x+ \frac{1}{x} = n$ Say n integer (given)
So $(x+ \frac{1}{x})^2 = n^2$
$x^2 + \frac{1}{x^2} = n^2-2$ is an integer
So true for 1 and true for 2
Let it be true for upto k
Now $x^k+ \frac{1}{x^k}$
$(x^k+ \frac{1}{x^k})(x+ \frac{1}{x})$
$= (x^{k+1} + \frac{1}{x^{k-1}}) + x^{k-1} + \frac{1}{x^{k+1}}$
So $(x^{k+1} + \frac{1}{x^{k+ 1}})= (x^k+ \frac{1}{x^k})(x+ \frac{1}{x})- (x^{k-1} + \frac{1}{x^{k-1}})$
If it is true for all n upto k so RHS is integer then LHS is integer so for n = k+ 1 it is an ingeger so the
induction step is proved
Hence proved