# MODULAR ARITHMATICS Find two numbers a and b bewen 50 and 100 saticfies these conditions: -The greatest common divisor of a and b is 3 (gcd(a,b) = 3) -The difference b-a geq 25 Preform Euclids algotirhm on these two numbers. Find whole numbers x and y such that 3 = ax + by

Discrete math
MODULAR ARITHMATICS
Find two numbers a and b bewen 50 and 100 saticfies these conditions:
-The greatest common divisor of a and b is $$\displaystyle{3}{\left({\gcd{{\left({a},{b}\right)}}}={3}\right)}$$
-The difference $$\displaystyle{b}-{a}\geq{25}$$
Preform Euclids algotirhm on these two numbers. Find whole numbers x and y such that $$\displaystyle{3}={a}{x}+{b}{y}$$

2020-12-04

Step 1
The required numbers a and b must lie between 50 and 100.
Given that the greatest common divisor of a and b is $$\displaystyle{\gcd{{a}}},{b}={3}.$$
Then, 3 divides both a and b.
In other words a and b are multiples of 3.
Next, list out all the multiples of 3 between 50 and 100. They are
$$\displaystyle{51},{54},{57},{60},{63},{66},{69},{72},{75},{78},{81},{84},{87},{90},{93},{96},{99}$$
Since $$\displaystyle{\gcd{{a}}},{b}={3}$$, a and b cannot have a common factor greater than 3.
The only factors of 51 are 1, 3, 17 and 51.
The factors of 51 greater than 3 are 17 and 51.
The multiples of 17 greater than 51 that lie between 50 and 100 are 68 and 85, both of which are not multiples of 3.
Also, the next multiple of 51 is 102, which is greater than 100.
Hence, from the above list of multiples of 3, 51 and any other number will have only 2 common factors, which are 1 and 3.
Thus, $$\displaystyle{\gcd{{51}}},{b}={3}$$ where b is a number in the above list of multiples of 3 between 50 and 100.
Take $$\displaystyle{a}={51}$$.
Step 2
The next condition is that $$\displaystyle{b}-{a}\geq{25}$$
Choose b such that $$\displaystyle{b}-{51}\geq{25}$$
Taking b as 78, the difference $$\displaystyle{78}-{51}={27}\geq{25}$$.
So, the numbers 51 and 78 satisfies all the required conditions.
Note that, there are many such pair of numbers.
For example, 51 and 84 is another pair of numbers satisfying both the conditions $$\displaystyle{\gcd{{a}}},{b}={3}$$ and $$\displaystyle{b}-{a}\geq{25}$$.
Here, we take $$\displaystyle{a}={51}{\quad\text{and}\quad}{b}={78}$$.
Now, we proceed by Euclid's division algorithm to find x and y such that $$\displaystyle{3}={51}{x}+{78}{y}$$.
First divide 78 by 51 and then divide the divisor by the remainder successively until the remainder is 3 and write in the form $$\displaystyle\div{n}{d}=\div{i}{s}{\quad\text{or}\quad}\times{q}{u}{o}{t}{i}{e}{n}{t}+{r}{e}{m}{a}\in{d}{e}{r}.$$
Step 3
Then,
$$\displaystyle{78}={51}\times{1}+{27}…{151}={27}\times{1}+{24}$$$$\displaystyle{227}={24}\times{1}+{3}$$ …3
Now, express the reminder 3 from the last step using previous remainders as follows.
$$\displaystyle{3}={27}-{24}\times{1}$$ from step $$\displaystyle{33}={27}-{243}={27}-{51}-{27}\times{1}$$ from step $$\displaystyle{23}={27}-{51}-{27}{3}={27}-{51}+{273}={2}\times{27}-{513}={2}\times{78}-{51}\times{1}-{51}$$ from step $$\displaystyle{33}={2}\times{78}-{51}-{513}={2}\times{78}-{2}\times{51}-{513}={2}\times{78}-{3}\times{51}$$
It can be noted that both $$\displaystyle{a}={51}$$ and $$\displaystyle{b}={78}$$ are whole numbers.
If x and y are also whole numbers, then they will be positive and $$\displaystyle{51}{x}+{78}{y}$$ will be a whole number much greater than 3.
Hence, one of x or y should be a negative integer.
Thus, the required integers x and y such that $$\displaystyle{3}={51}{x}+{78}{y}$$ are $$\displaystyle{x}=-{3},{y}={2}{a}{s}{3}={51}\times-{3}+{78}\times{2}.$$