Solving a Single Congruence Equation

[Thomas Klemm]

(07-25-2015 12:54 PM)Bunuel66 Wrote:  Strictly from an algorithmic standpoint (I haven't checked in terms of speed), it could be more straightforward to use Fermat's little theorem who says in a nutshell that if A is prime relatively to N then A^(N-1)=1 Mod N which is equivalent to say that A^(N-2) is an inverse of A Mod N.

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.\)

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\)

Quote:As A^(N-2) can be computed Mod N at every step the risk of overflow is reduced.

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

Kind regards
Thomas