Mathematical Background
If n is an integer, then the integers modulo n form a ring. If n=pq where p and q are primes, then the Chinese remainder theorem tells us that
The group of units of any ring form a group, and the group of units in is traditionally denoted 
.
From the isomorphism above, we have
as an isomorphism of groups. Since p and q were assumed to be prime, the groups and are cyclic of orders p-1 and q-1 respectively. If d is a divisor of p-1, then the set of dth powers in form a subgroup of index d. If gcd(d,q-1) = 1, then every element in is a dth power, so the set of dth powers in is also a subgroup of index d. In general, if gcd(d,q-1) = g, then there are (q-1)/(g) dth powers in, so the set of dth powers in has index dg. This is most commonly seen when d=2, and we are considering the subgroup of quadratic residues, it is well known that exactly one quarter of the elements in are quadratic residues (when n is the product of exactly two primes, as it is here).
The important point is that for any divisor d of p-1 (or q-1) the set of dth powers forms a subgroup of
Read more about this topic: Higher Residuosity Problem
Famous quotes containing the words mathematical and/or background:
“What he loved so much in the plant morphological structure of the tree was that given a fixed mathematical basis, the final evolution was so incalculable.”
—D.H. (David Herbert)
“Silence is the universal refuge, the sequel to all dull discourses and all foolish acts, a balm to our every chagrin, as welcome after satiety as after disappointment; that background which the painter may not daub, be he master or bungler, and which, however awkward a figure we may have made in the foreground, remains ever our inviolable asylum, where no indignity can assail, no personality can disturb us.”
—Henry David Thoreau (1817–1862)