Solve the following set of equations for positive integers a and b:

1919(a)(b) mod 5107 = 1
1919(a+1)(b-1) mod 5108 = 5047
1919(a+2)(b-2) mod 5109 = 1148
1919(a+3)(b-3) mod 5110 = 3631
1919(a+4)(b-4) mod 5111 = 2280

(In reply to re(5): Solution ------ can you check? by K Sengupta)

KS,

With my appologies, it seems that you are absolutely right. I found this problem in a site, followed its solution, but I didn΄t notice the mistake in the rhs sign. And then, it was presented the two wrong solutions. And the site, may I say, it΄s "above any suspicion!!!"

About the "a little trial and error" to find the modular inverse, do you know the following method?

1919 mod 5107

5107 = 1919*2 + 1269

1919 = 1269*1 + 650

1269 = 650*1 + 619

650 = 619*1 + 31

619 = 31*19 + 30

31 = 30*1 + 1

 

1 = 31 – 30

1 = 31 – (619 – 31*19) = 31*20 – 619

1 = (650 – 619)*20 – 619 = 650*20 – 21*619

1 = 650*20 – 21*(1269 – 650) = - 21*1269 + 41*650

 

1 = -21*(1919 – 650) + 41*650 = - 21*1919 + 62*650 = - 21*1919 + 62*(1919 – 1269) =  - 62*1269 + 41*1919

 

1 = - 62*(5107 – 2*1919) + 41*1919 = 165*1919 - 62*5107

 

The number being multiplied by the original key (smaller number) is the modular inverse... 165, which is 165 in mod 5107.

165 * 1919 ≡ 1 (mod 5107)

 

So:

1919(ab) ≡ 1 (mod 5107)

1919*165(ab) ≡ 1*165 (mod 5107)

(ab) ≡ 165 (mod 5107)

Edited on August 4, 2008, 9:15 am

Posted by pcbouhid on 2008-08-04 09:11:30