Use Euclid's algorithm to find a multiplicative inverse of 15 mod 88, hence solve the linear congruence 15x=20(mod 88)
So far I have:
88=5x15+13
15=1x13+2
Backwards substitution gives
15v+18w=1
1=15-1x13
=15-1(88-5x15)
=15x15-1x88
now very stuck what to do from here:(
To find the multiplicative inverse of 15 mod 88 using Euclid's algorithm, you need to continue the backward substitution until you find the coefficients of 15 and 88.
From your calculations:
1 = 15 - 1(88 - 5x15)
= 15x15 - 1x88
Now, substitute 15 in terms of 88 and 13 (from the second step of Euclid's algorithm):
1 = (15x15 - 1x88)
= (15x15 - 1(88 - 5x15))
= 6x15 - 1x88
Now, substitute 15 in terms of 88 and 13 again:
1 = 6(15 - 1x13) - 1x88
= 6x15 - 6x13 - 1x88
= -6x13 + 6x15 - 1x88
Now, we can see that the coefficient of 15 is 6, which indicates that 6 is the inverse of 15 mod 88. Therefore, the multiplicative inverse of 15 mod 88 is 6.
To solve the linear congruence 15x ≡ 20 (mod 88), multiply both sides of the congruence by the multiplicative inverse of 15 (which is 6):
6x(15x) ≡ 6x(20) (mod 88)
90x ≡ 120 (mod 88)
Now let's simplify the congruence:
90x ≡ 120 (mod 88)
2x ≡ 32 (mod 88)
To find the solution of this congruence, divide both sides by the greatest common divisor (GCD) of 2 and 88, which is 2:
2x/2 ≡ 32/2 (mod 88)
x ≡ 16 (mod 88)
Therefore, the solution to the linear congruence 15x ≡ 20 (mod 88) is x ≡ 16 (mod 88).
To find the multiplicative inverse of 15 mod 88, we need to continue with Euclid's Algorithm to express 15x + 88y = gcd(15, 88) as 15v + 18w = 1.
From where you left off:
1 = 15 - 1(88 - 5x15)
1 = 15 - 1(88 - 75)
1 = 15 - 1(75 - 1x15)
1 = 2x15 - 1x75
1 = 2x15 - 75
Now we can see that the coefficient of 15 is 2, which is the inverse of 15 modulo 88. Therefore, the multiplicative inverse of 15 mod 88 is 2.
Now, to solve the linear congruence 15x = 20 mod 88, we can multiply both sides of the congruence by the multiplicative inverse of 15 modulo 88, which is 2:
2(15x) = 2(20) mod 88
30x = 40 mod 88
Simplifying:
30x = 40 mod 88
30x = 40 + 88k (where k is an integer)
Dividing both sides by the greatest common divisor of 30 and 88, which is 2:
15x = 20 + 44k
The general solution for this congruence is:
x ≡ (20 + 44k) / 15 mod 88, where k is an integer.