Solving a Single Congruence Equation

[Bunuel66]

Quote:Fermat's little theorem:
If p is a prime number and a is not divisible by p then: \(a^{p-1} \equiv 1 \pmod p.\)

Yes you're right with the restriction you mention, but in that case it seems to be possible to use Bezout/Merignac for computing the inverse:

1/ if A and N are coprimes, then it exist u,v as: A.u+N.v=1 then u=\(A^{-1}\) Mod N
Ax=B Mod N => uAx=uB Mod N =>x=uB Mod N

2/ if A and N are not coprimes it exists C dividing A and N then let A=A/C, N=N/C and B=B/C

2.a if C doesn't divide B there is no solution

2.b if C divides B we are back to 1 as A, N are now coprimes.
x is solution of Ax=B mod N

Examples:
5x=3 Mod 17 Using Euclide extended one finds 7*5-2*17=1 then \(5^{-1}\)=7 Mod 17
x=3*7 Mod 17=4 Mod 17

12x=6 Mod 15 according to the above discussion: => 4x=2 Mod 5 and \(4^{-1}\)=4 Mod 5
then x=4*2 Mod 5 => x=3 Mod 5

Quote:Euler's theorem:
If n and a are coprime positive integers, then: \(a^{\varphi (n)} \equiv 1 \pmod{n}\)

Thus you'd first had to calculate \(\varphi (n)\).

For the given example this is: \(\varphi (999999999999)=461894400000\)

Well, it seems that \(\varphi (n)\) is not needed in the above approach. That said, I'm ready to admit that the extended Euclid Algorithm applied directly will probably lead to computations of that complexity. But it is certainly possible to conduct the computations in modular form for limiting the expansion of numbers.

Quote:How do you intend to calculate 999999999989^461894399999 mod 999999999999 without overflow?

It is mainly a question of what you have in hand. If you are able to compute at least the square of your number without overflow then the modulo operation will limit the expansion at every step
of the loop. It is not that difficult to write algorithms for the 4 elementary operations working on 24 figures if you have operators working on a lower number. It is a bit a brute force solution, but is should work.

There is certainly a more astute approach?

My 3 cents....