RSA is based on a remarkable, and a very non-obvious, even strange number theoretic formula, conjectured by Fermat (1601-1665), and proven almost a century later (1736) by Euler who generalized it in 1760, to say:
If gcd(a,n)=1 then afi(n) = 1 mod n
where fi(n) is 'Euler Totient Function' that simply counts how many integers between 1 and (n-1) are co-primes with n.
Looking back on the easy Euler's proof, one wanders why this posed such a tough nut to crack for the excellent mathematicians of the 18th century, and one further wanders how many easy short cuts to our present day ciphers are one brilliant insight away from a compromising discovery.
Euler observed that the totient function counts all the residues r1, r,2... rfi(n) of n, but the series: ar1, ar,2... arfi(n) also features the same residue. Euler then realized that the content of these two lists is the same -- albeit in a different order . And hence the multiplication of the two series will yield the same result:
(ar1)*( ar,2)*... *(arfi(n)) = (r1)*( r2)*... *(rfi(n)) mod n
And since gcd(ri,n)=1 for i=1,2,...fi(n), it follows:
a*a*......a = 1 mod n
afi(n) = 1 mod n
-- and this remarkable relationship is proven!