Doubt in modules

Question

where Theta(n) = 216

 

can someone please tell me how 31 is calculated 

 

Please some one help me in this

Comments

Please someone help me on this

Answer 1

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

Comments

really thank you for answer

but looking at answer , i think we need to make it shorter for exam time.

may be at third step it self we come to know about 30 . So we can try nearby number may be 29 or 31

will it be correct approach please reply.