# Math Help - Split congruence into two pieces

1. ## Split congruence into two pieces

$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?

2. Originally Posted by szpengchao
$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 $N=AB$, then:

$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