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:
“An accurate charting of the American woman’s progress through history might look more like a corkscrew tilted slightly to one side, its loops inching closer to the line of freedom with the passage of time—but like a mathematical curve approaching infinity, never touching its goal. . . . Each time, the spiral turns her back just short of the finish line.”
—Susan Faludi (20th century)
“... every experience in life enriches one’s background and should teach valuable lessons.”
—Mary Barnett Gilson (1877–?)