RSA is based on a remarkable, and a very nonobvious, even strange number theoretic formula, conjectured by Fermat (16011665), and proven almost a century later (1736) by Euler who generalized it in 1760, to say:
If gcd(a,n)=1 then a^{fi(n)} = 1 mod n
where fi(n) is 'Euler Totient Function' that simply counts how many integers between 1 and (n1) are coprimes 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 r_{1}, r,_{2}... r_{fi(n)} of n, but the series: ar_{1}, ar,_{2}... ar_{fi(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:
(ar_{1})*( ar,_{2})*... *(ar_{fi(n)}) = (r_{1})*( r_{2})*... *(r_{fi(n)}) mod n
And since gcd(r_{i},n)=1 for i=1,2,...fi(n), it follows:
a*a*......a = 1 mod n or : a^{fi(n)} = 1 mod n
 and this remarkable relationship is proven!

