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.

Guest Oct 24, 2018

#1**+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)**

Guest Oct 24, 2018

edited by
Guest
Oct 24, 2018