Please someone help me on this

0 votes

where Theta(n) = 216

can someone please tell me how 31 is calculated

Please some one help me in this

1 vote

Best answer

x = $7^{-1}\ mod\ 216$

=> $(7 * x)\ mod\ 216 = 1$

We use the extended euclidean algorithm to compute x

$216 = 7 * 30 + 6\ (1)$

$7 = 6 * 1 + 1\ (2)$

In equation (2), we get 1 as remainder implying GCD (7,216) = 1 , therefore there exists a multiplicative inverse of 7 modulo 216

From equation (2)

$1 = 7 - 6 \ (3)$

From equation (1)

$6 = 216 - 7 * 30\ (4)$

Substituting 6 of equation (4) in equation (3)

$1 = 7 - (216 - 7 * 30)$

$=> 1 = 7 * 31 - 216$

Taking mod 216 on both sides

1 = (7*31) mod 216 - 216 mod 216

=> 1 = (7*31) mod 216

Thus x = 31

=> $(7 * x)\ mod\ 216 = 1$

We use the extended euclidean algorithm to compute x

$216 = 7 * 30 + 6\ (1)$

$7 = 6 * 1 + 1\ (2)$

In equation (2), we get 1 as remainder implying GCD (7,216) = 1 , therefore there exists a multiplicative inverse of 7 modulo 216

From equation (2)

$1 = 7 - 6 \ (3)$

From equation (1)

$6 = 216 - 7 * 30\ (4)$

Substituting 6 of equation (4) in equation (3)

$1 = 7 - (216 - 7 * 30)$

$=> 1 = 7 * 31 - 216$

Taking mod 216 on both sides

1 = (7*31) mod 216 - 216 mod 216

=> 1 = (7*31) mod 216

Thus x = 31