section{A Note on the Carmichael Function}%22
markboth{Articles}{A Note on the Carmichael Function}
vspace{4.2cm}
The well-known Euler's theorem states that
$x^{varphi (m)}equiv 1pmod m$
for every positive integer $m$ and every integer $x$ coprime to $m$, where $varphi $ is the Euler's
totient function.
However, with some exceptions, $varphi (m)$ is usually not the
least positive integer $t$ so that
$x^tequiv 1pmod m$
holds for all integers $x$ with
$gcd(x,m)=1$
and can be "optimized" to the so-called Carmichael Function $lambda (m)$.
Properties of this function keep appearing in Olympiad problems and
can often be very useful.
The purpose of this note is to state and prove some
of these properties and to give some examples of how they can be applied in
Olympiad problems.
subsection{Introduction}
The following problem was given at the 3rd round of the 2006 Iranian National
Olympiad.
{f Problem 1.}
{it Let $n$ be a positive integer and let $d$ be the least positive integer,
such that
$a^dequiv 1pmod n$
for every integer $a$ with $gcd(a, n) = 1$.
Prove that there exists an integer $b$ so that $ord_n(b) = d.$
}
We will see that this problem is a special case of a more general result, but
before proving it, we shall cover some theory.
{f Definition 1.}
For a positive integer $m$ and an integer $x$ with $gcd(x,m) = 1,$
the order of $x$ modulo $m$, denoted by $ord_m(x)$, is the least positive integer $t$,
so that $x^tequiv 1pmod m$.
Euler's theorem implies that $ord_m(x)le varphi (m)$.
{f Lemma 1.}
{it Let $m$ be a positive integer and $x$ be an integer coprime to $m$.
Then
$x^nequiv 1pmod m$ if and only if $ord_m(x)mid n$.
Furthermore,
$x^{n_1}equiv x^{n_2}pmod m$
if and only if
$ord_m(x)mid (n_1-n_2)$,
i.e.,
$n_1equiv n_2pmod {ord_m(x)}$.
}
{f Proof.}
Let $d=ord_m(x)$.
It is clear that $dmid n$ implies
$x^nequiv 1pmod m$.
On the other hand,
$x^nequiv 1pmod m$,
then there are integers $q,r$ such that
$n=qd+r$, $0le rle d-1$, and
$$x^nequiv x^{qd+r}equiv x^requiv 1pmod m.$$
But $0le rle d-1$, so $r=0$.
{f Definition 2.}
Let $m$ be a positive integer.
An integer $g$ is called a primitive root modulo m if $ord_m(g)=varphi (m)$.
Unfortunately, roots do not exist for every positive integer $m$.
{f Lemma 2.}
{it Let $m$ be a positive integer greater than 1.
Then primitive roots
modulo $m$ exist if and only if $m$ has the form 2, 4, $p^k$ or $2p^k$ where $p$ is an
odd prime number and $k$ is a positive integer.
}
This theorem is very well known, so we skip the rather long proof of it
(interested readers can find a proof in [2]).
subsection{The Carmichael Function}
{f Definition 3.}
For a positive integer $m$, $lambda (m)$ denotes the least positive integer
$t$ so that
$x^tequiv 1pmod m$
for all integers $x$ with $gcd(x,m)=1$.
$lambda (m)$ is the so-called Carmichael Function.
{f Lemma 3.}
{it Let $m$ be a positive integer.
Then
$lambda (m)mid t$ if and only if $x^tequiv 1pmod m$
for all integers $x$ coprime to $m$.
}
The proof of Lemma 3 is similar to the proof of Lemma 1 and is left as an
exercise to the reader.
Note that Euler's theorem implies $lambda (m)le varphi (m)$.
It is clear that if $m$ has primitive roots, then
$lambda (m)=varphi (m)$.
We will now find a formula for $lambda (m)$.
{f Lemma 4.}
{it Let $kge 3$ be an integer.
Then
$lambda (2^k)=2^{k-2}$.
}
{f Proof.}
We first observe that $x^2equiv 1pmod 8$ for all odd integers $x$.
Using induction, we can assume that $x^{2^{k-2}}equiv 1pmod {2^k}$
for all odd $x$ and some $kge 3$.
Then either
$$x^{2^{k-2}}equiv 1pmod {2^{k+1}}
qmbox{or}q
x^{2^{k-2}}equiv 1+2^kpmod {2^{k+1}}.$$
However, we have
$x^{2^{k-1}}equiv 1pmod {2^{k+1}}$
in both cases, implying
$lambda (2^k)le 2^{k-2}$.
Now, let $x$ be an odd integer so that
$ord_{16}(x)=4$
(i.e., each integer congruent to 3 or 5 modulo 8).
We clearly have
$ord_8(x)=2$.
By induction, we can assume that
$ord_{2^k}(x)=2^{k-2}$
and
$ord_{2^{k+1}}(x)=2^{k-1}$ for some $kge 3$.
Then
$x^{2^{k-2}}equiv 1pmod {2^k}$
but
$x^{2^{k-2}}
otequiv pmod {2^{k+1}}$,
implying
$x^{2^{k-2}}equiv 1+2^kpmod {2^{k+1}}$.
Hence, either
$$x^{2^{k-2}}equiv 1+2^kpmod {2^{k+2}}
qmbox{or}q
x^{2^{k-2}}equiv 1+2^k+2^{k+1}pmod {2^{k+2}}.$$
In both cases we have
$$x^{2^{k-1}}equiv 1+2^{k+1}
otequiv 1pmod {2^{k+2}}.$$
Thus
$ord_{2^{k+2}}(x)>2^{k-1}$.
On the other hand,
$ord_{2^{k+2}}(x)mid varphi (2^{k+2})=2^{k+1}$
by Lemma 1, so
$ord_{2^{k+2}}(x)in {2^k,2^{k+1}}$.
But
$ord_{2^{k+2}}(x)$ cannot exceed $lambda (2^{k+2})$
and we already know that
$lambda (2^{k+2})le 2^k$.
It follows that
$ord_{2^{k+2}}(x)=2^k$ and thus
$lambda (2^{k+2})=2^k$.
The proof of Lemma 4 also proves the following lemma.
{f Lemma 1.}
{it For each $x$ congruent to $3$ or $5$ modulo $8$,
$$ord_{2^k}(x)=lambda (2^k)=2^{k-2}$$
for all $kge 3$.
}
Now, let $a$ and $b$ be two coprime positive integers and let
$d_1=lambda (a)$, $d_2=lambda (b)$, $d=lambda (ab)$.
Then $x^dequiv 1pmod {ab}$
for any integer $x$ coprime to $ab$, so
$$x^dequiv 1pmod a
qmbox{and}q
x^dequiv 1pmod b
eqno(1)$$
for all integers $x$ coprime to $ab$.
Now, from Lemma 3 it follows that $d_1mid d$ and $d_2mid d$
is a necessary and sufficient condition for (1) and since $d$ is the least
positive integer satisfying (1), it follows that
$d={
m lcm}(d_1,d_2)$.
As a result we have the following lemma.
{f Lemma 5.}
{it For any coprime positive integers $a$ and $b$,
$$lambda (ab)={
m lcm}(lambda (a),lambda (b)).$$
}
We see that Lemma 2, 4, and 5 already give a complete formula for $lambda (m)$.
We summarize:
{f Theorem 1.}
{it Let $m$ be a positive integer greater than $1$.
Then
$$lambda (m)=
left{a{ll}
varphi (m) & mbox{for } m=2,4,p^k, mbox{where} pge 3 mbox{is prime}\
2^{k-2} & mbox{for } m=2^k, mbox{where} kge 3\
{
m lcm}(lambda (p_1^{k_1}),ldots ,lambda (p_r^{k_r})) & mbox{for } m=dsprod_{i=1}^r p_i^{k_i},
mbox{where} p_imbox{ are distinct}\
& mbox{prime numbers}.
ea
ight.$$
}
We can now return to the beginning of this note and solve Problem 1.
{f Lemma 6.}
{it For any positive integer $m$, there exists an integer $x$ so that
$$ord_m(x)=lambda (m).$$
}
{f Proof.}
Let $m=p_1^{k_1}ldots p_r^{k_r}$
be the prime factorization of $m$ and let $x$ be a solution of the congruence system
$$xequiv g_ipmod {p_i^{k_i}}mbox{ for } i=1,ldots ,r,$$
where $g_i$ are integers satisfying
$ord_{p_i^{k_i}}(x)=lambda (p_i^{k_i})$
respectively (they exist by Lemma 2 and 1).
Such an $x$ exists by the Chinese Remainder Theorem.
Then by Lemma 1,
$lambda (p_i^{k_i})=ord_{p_i^{k_i}}(x)mid ord_m(x)$ for all $i=1,ldots ,r$.
Hence
$$ord_m(x)ge {
m lcm}(lambda (p_1^{k_1}),ldots ,lambda (p_r^{k_r}))=lambda (m).$$
But $ord_m(x)$ cannot exceed $lambda (m)$, so $ord_m(x)=lambda (m)$.
Lemma 6 can be generalized to
{f Theorem 2.}
{it Let $m$ and $d$ be positive integers.
Then there exists an integer $x$ with
$ord_m(x)=d$ if and only if $dmid lambda (m)$.
}
{f Proof.}
If $ord_m(x)=d$ for some $x$, then Lemma 1 implies $dmid lambda (m)$.
On the other hand, if $dmid lambda (m)$, let $z$ be an integer with
$ord_m(z)=lambda (m)$
(which exists by Lemma 6),
$e=lambda (m)/d$, and $x=z^e$.
Then
$ord_m(x)=d$ because
$$x^d=z^{ed}=z^{lambda (m)}equiv 1pmod m$$
and
$ord_m(x)<d$ would imply
$ord_m(z)<ed=lambda (m)$, a contradiction.
The applications of the properties of the Carmichael Function are, when
possible, not always as obvious as it has been in Problem 1.
The following problem illustrates another kind of usage.
{f Problem 2.}
{it Prove that for any positive integer $k$, there is a positive integer
$n$ so that $2^kmid 3^n+5$.
}
{f Solution.}
We will only discuss $kge 3$.
The statement is true for $k = 3$, just
take $n = 1$ (we need this for the purpose of induction).
It follows from Lemma 1 that
$ord_{2^k}(3)=lambda (2^k)=2^{k-2}$.
However, since
$$ord_{2^{k+1}}(3)=lambda (2^{k+1})=2^{k-1}>2^{k-2}=ord_{2^k}(3),$$
from Lemma 1 it follows that
$3^{i+2^{k-2}}equiv 3^ipmod {2^k}$
but
$3^{i+2^{k-2}}
otequiv 3^ipmod {2^{k+1}}$
and thus
$3^{i+2^{k-2}}equiv 3^i+2^kpmod {2^{k+1}}$.
Hence, if $3^iequiv -5pmod {2^k}$,
then either
$3^iequiv -5pmod {2^{k+1}}$
or
$3^{i+2^{k-2}}equiv -5pmod {2^{k+1}}$.
section*{Bibliography}
i
item[{[1]}]
Mathlinks, {it Order,}\
http://www.mathlinks.ro/Forum/viewtopic.php?t=108204
item[{[2]}]
Mathlinks, {it Primitive root,}\
http://www.mathlinks.ro/Forum/viewtopic.php?t=55473
item[{[3]}]
Mathlinks,
$(2^k)mid (3^m+5)$,\
http://www.mathlinks.ro/Forum/viewtopic.php?t=1912
ei
igskip
hfill
{Large Yimin Ge, Vienna, Austria}
%%%%%%%