Learn to build web apps and services, IoT apps, and mobile backends by covering the fundamentals of ASP.NET Core and exploring the core foundations for app libraries.

( 15 * q ) mod 17 = 1

I am trying to figure an easy wat to compute this , to find q . From the example i know q = 8 , but am finding a way how they were able to get to this answer.

detailed explanation will be appreciated

I am trying to figure an easy wat to compute this , to find q . From the example i know q = 8 , but am finding a way how they were able to get to this answer.

detailed explanation will be appreciated

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

I don't know whether this is the kind of explanation you are expecting, but here goes:

If you look at the equation, it simply means that q is a number (integer in this case) which when multiplied by 15 and divided by 17 leaves 1 as remainder.

Manually, we needs to start counting from 1 onwards.

e.g.

(15*1) mod 17 = 15 mod 17 = ((17*0)+15) mod 17 = 15

(15*2) mod 17 = 30 mod 17 = ((17*1)+13) mod 17= 13

(15*3) mod 17 = 45 mod 17 = ((17*2)+11) mod 17 = 11

If you count in this manner, you'll see that the first number where the required condition (1 as remainder) is met is when q=8.

(15*8) mod 17 = 120 mod 17 = ((17*7)+1) mod 17 = 1

Speaking from the programming perspective, you can use the q as variable and state the equation as the condition which needs to be met, you'll get the same answer.

Hope this helps.

Warm regards,

Sarang

q = 15^(-1) mod 17; i.e., q is the modulo multiplicative inverse of 15 mod 17

Since 17 is prime (and therefore 15 and 17 are mutually prime, then we know that there exists a solution to this problem.

Here is an introduction to Modular multiplicative inverse:

http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Here is code from http://snippets.dzone.com/posts/show/4256 on computing efficiently the modulo inverse (I did not test it):

```
int modInverse(int a, int n) {
int i = n, v = 0, d = 1;
while (a>0) {
int t = i/a, x = a;
a = i % x;
i = x;
x = d;
d = v - t*x;
v = x;
}
v %= n;
if (v<0) v = (v+n)%n;
return v;
}
```

http://userpages.umbc.edu/~rcampbel/NumbThy/Class/BasicNumbThy.html#Modular-GCD

==

( 15 * q ) mod 17 = 1

-> 15q = 17k + 1

-> 15q - 17k = 1; solve for q

==

From the process described in http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm we get:

1 = 17(-1) + 15*8

If you let q=8 and k=1 you get 1 = 17(-k) + 15*q = 15*q - 17k

i.e., 1 = 15*q - 17k

and q = 8, the multiplicative inverse of 15 mod 17

```
Step Q Remainder Substitute Combine terms
1 17 17 = 17*1 + 15*0
2 15 15 = 17*0 + 15*1
3 17/15=1 2=17-15*1 2 = 17*1 - 15*1
4 15/2 =7 1=15-2*7 = 15-(17*1-15*1)*7
= 15 -17*1 + 15*7 1 = 17(-1) + 15*8
5 2/1 =2 0 End of algorithm
```

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial