if 13* D = 1 mod 60 then D = 37 how?

16,912

Solution 1

i think this is what you are looking for

Verifying the answer is easy, finding it in the first place, a little more work.

Verification:

13 * 37 = 481 
481 = 8 * 60 + 1

Hence if you divide 13 * 37 by 60 you have remainder 1.

Alternate answers:

Any integer of the form (37 + 60 k) where k is any integer is also a solution. (97, -23, etc.)

To find the solution you can proceed as follows:
Solve:

13 d = 1 + 60 k 
mod 13:
0 = 1 + 8k (mod 13) 
8k = -1 (mod 13) 
Add 13's until a multiple of 8 is found: 
8k = 12 or 25 or 38 or 51 or 64 .... aha a multiple of 8! 
k = 64 / 8 = 8 
Substitute k = 8 back into 13 d = 1 + 60 k 
13 d = 1 + 8 * 60 = 481 
481 /13 = 37 

and that is the answer.

Solution 2

Use the extended Euclidean algorithm to compute integers x and y such that

13*x+60*y=1

Then x is the answer you're looking for, mod 60.

Share:
16,912
AmanS
Author by

AmanS

Updated on June 07, 2022

Comments

  • AmanS
    AmanS over 1 year

    I am solving an example problem, RSA algorithm
    I have been given two prime numbers 7 and 11. Let's say p=7 and q=11
    I have to calculate the decryption key, d, for some encryption key, e.

    Firstly I calculated n=p*q which implies that n=77.

    Suppose that e=13,
    to calculate d I used the formula d*e = 1 mod fi, where fi=(p-1)(q-1), and so fi=60

    The final equation becomes 13*d = 1 mod fi

    According to some solved example d is calculated to be 37, how is this result obtained?

    Any help would be appreciated.

    • Aki Suihkonen
      Aki Suihkonen almost 10 years
      en.wikipedia.org/wiki/Linear_congruence_theorem . When the modulus is small (e.g. uint32_t), you can write a program to test each candidate and get the result in no time.
    • Maarten Bodewes
      Maarten Bodewes almost 10 years
      This question appears to be off-topic because it is not about programming.
  • AmanS
    AmanS almost 10 years
    what is the simplest method to calculate x because in your equation y is also unknown