+0  
 
+1
84
1
avatar

I really need help in solving this modular equation. 23^11 mod n =1,189,872. What is the smallest positive n that will satisfy the equation? I would greatly appreciate any help. Thank you. 

 Oct 24, 2018
 #1
avatar
+1

I'm sorry that I don't know how to solve such a modular equation, with such large integers, in any formal manner. Maybe heureka or somebody else can provide such a solution.

However, I can easily write a very short computer code to search for the smallest positive n. Just in case you or your teacher are interested, here is the computer code that searched from 1 to 2,000,000 numbers in a matter of seconds and came up with: 1,234,577 as the smallest positive n.

{a=23^11; b=2000000; c=(1); n=2; if((a mod n)==1189872,c=(c,n),0); n++; if(n<=b,gotor-2,c)}

Check: 23^11 mod 1,234,577 =1,189,872. Good luck to you.

P.S. There are 2 larger numbers that also satisfy the equation:( 6,172,885, 8,123,897)

 Oct 24, 2018
edited by Guest  Oct 24, 2018

8 Online Users

avatar
avatar