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

sagnuhh

sagnuhh

Answered question

2020-12-03

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 ba25
Preform Euclids algotirhm on these two numbers. Find whole numbers x and y such that 3=ax+by

Answer & Explanation

wornoutwomanC

wornoutwomanC

Skilled2020-12-04Added 81 answers

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 gcda,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
51,54,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99
Since gcda,b=3, a and b cannot have a common factor greater than 3.
We start with the number 51.
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, gcd51,b=3 where b is a number in the above list of multiples of 3 between 50 and 100.
Take a=51.
Step 2
The next condition is that ba25
Choose b such that b5125
Taking b as 78, the difference 7851=2725.
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 gcda,b=3 and ba25.
Here, we take a=51andb=78.
Now, we proceed by Euclid's division algorithm to find x and y such that 3=51x+78y.
First divide 78 by 51 and then divide the divisor by the remainder successively until the remainder is 3 and write in the form ÷nd=÷isor×quotient+remader.
Step 3
Then,
78=51×1+27151=27×1+24227=24×1+3 …3
Now, express the reminder 3 from the last step using previous remainders as follows.
3=2724×1 from step 33=27243=275127×1 from step 23=2751273=2751+273=2×27513=2×7851×151 from step 33=2×7851513=2×782×51513=2×783×51
It can be noted that both a=51 and b=78 are whole numbers.
If x and y are also whole numbers, then they will be positive and 51x+78y 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 3=51x+78y are x=3,y=2as3=51×3+78×2.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?