Thread: Split congruence into two pieces

$\displaystyle a^{N-1}=1 \ mod \ N $

if we now N is composite, how can u split this into two congruences which are equivalent to original one?

Originally Posted by szpengchao

$\displaystyle a^{N-1}=1 \ mod \ N $

if we now N is composite, how can u split this into two congruences which are equivalent to original one?

If $\displaystyle N=AB$, then:

$\displaystyle a^N = a^A a^{B-1}\equiv 1 \ \text{mod} \ N = [a^A \text{ mod } N][a^{B-1} \text{ mod } N] \text{ mod } N$

CB