$\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?
Follow Math Help Forum on Facebook and Google+
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
View Tag Cloud