Re: A question about modular exponentiation
From: Bill Dubuque (firstname.lastname@example.org)
From: Bill Dubuque <email@example.com> Date: 24 Apr 2003 11:23:24 -0400
Paul Schlyter <firstname.lastname@example.org> wrote:
> In RSA, keys are usually generated in this way:
> 1. Generate two primes, p and q, and compute the modulus n = pq
> 2. Choose a public exponent e, a common choice is e = 65537
> 3. Compute the private exponent from:
> d = 1/e mod (p-1)(q-1)
> One can also compute the private exponent in a slightly different way:
> d' = 1/e mod LCM(p-1,q-1)
> [...] my question is: when d and d' are different, does always both
> of them work with the one and same public exponent e and modulus n ?
My prior post was garbled by cut'n paste. Here's the correction.
Yes, if M encrypts to E = M^e mod n, then E^d mod n decrypts it
if (M^e)^d = M (mod n) for all M. Since n is squarefree, this is
true if y(n)|ed-1 [see my first post below, but replace phi(m)
by y(m) = Carmichael lambda, explained in my second post below].
For n = pq the equations below yield y(pq) = lcm(p-1,q-1), so
d correctly descrypts if lcm(p-1, q-1)|ed-1. But this holds true
since by definition of d, (p-1)(q-1)|ed-1, so your observation
follows from: lcm(p-1,q-1)|(p-1)(q-1)|ed-1.
From: Bill Dubuque <email@example.com>
Subject: Re: x^3-x always divisible by 6
"Christopher Anderson" <firstname.lastname@example.org> writes:
> While in an interview I was asked why when a value of x is placed into
> x^3-x it is divisible by 6. ... How do I show this using algebra?
More generally, for any squarefree integer m, and any integer x,
phi(m) + 1
x = x (mod m) 
Recall m is squarefree means that each prime occurs to power at
most one in m, say m = p q ... s, and in this special case the
Euler totient function is simply phi(m) = (p-1) (q-1) ... (s-1).
In your case we have m=6=2*3 so phi(m)=1*2 and x^3=x (mod 6).
To prove  above we first prove that it holds (mod p) for
any prime p dividing m: clearly  holds if x = 0 (mod p);
otherwise  follows from Fermat's Little Theorem (FlT) as
phi(m) + 1 p-1 q-1 ... s-1 + 1
x = x
p-1 q-1 ... s-1
= (x ) * x
= x since x = 1 (mod p) by FlT
Thus since x^(phi(m)+1)-x is divisible by the distinct primes
p,q,...,s it must be divisible by their product m = p q ... s
(a special case of the Chinese Remainder Theorem).
Note that the above proof fails if m is not squarefree since
x^(p^(n-1)*(p-1)) = 1 (mod p^n) need not hold if p divides x,
e.g. consider x=p=n=2: 2^2 != 1 (mod 4); thus x^3 != x (mod 4).
In general, for any finite group G of size n, all elements x in G
satisfy x^n = 1. Fermat's Little Theorem is a very special case.
These are basic results that can be found in all elementary texts
on algebra, groups, number theory, or finite fields, etc.
From: Bill Dubuque <email@example.com>
Date: 30 May 2002 02:57:46 -0400
Subject: Re: elementary number theory question
Chris Nolen <firstname.lastname@example.org> wrote:
> In my number theory homework I showed that if n is an integer
> not divisible by 2 or 3 then n^2 + 23 must be divisible by 24.
> Is there a general theory that relates to this?
You showed that a^2 = 1 (mod 24) if (a,24) = 1. More generally,
k = y(m) => a^k = 1 (mod m) if (a, m) = 1
where y(m) is the Carmichael lambda function, defined as is the
Euler phi function on prime powers, but combined via lcm vs. times:
y(2 ) = 2 for e>2; y(4) = 2, y(2) = y(1) = 1
y(p ) = p (p-1) for odd prime p
i j i j
y(p q...) = lcm( y(p ), y(q ), ... )
In your case y(24) = y(2^3*3) = lcm(2,2) = 2, as you showed,
and it's easy to see that 24 is the largest m with y(m) = 2.
In group theoretic language one says the y(m) is the exponent
of the unit group of Z/(m), i.e. the smallest k such that
x^k = 1 for all elts x in group [x coprime to n in Z/(m)]