The Gateway to Computer Science Excellence
0 votes
33 views

where Theta(n) = 216

 

can someone please tell me how 31 is calculated 

 

Please some one help me in this

in Computer Networks by Loyal (5.3k points)
reopened by | 33 views
0
Please someone help me on this

1 Answer

+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
by (421 points)
selected by
0
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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
198,337 comments
105,026 users