Etap wojewódzki 2011-2012 arkusz, Nauka, Olimpiady, konkursy przedmiotowe, woj. śląskie
Etap wojewódzki 2011-2012 klucz, Nauka, Olimpiady, konkursy przedmiotowe, woj. śląskie
Etap rejonowy 2010-2011, Nauka, Olimpiady, konkursy przedmiotowe, woj. śląskie
etn - cwiczenia nr 4, WAT, SEMESTR V, elementy teori niezawodnosci, Etn - Zaliczenie, Etn - Zaliczenie, materialy kapalki - starsze
Etap wojewódzki 2006-2007 klucz, GEOGRAFIA, olimpiada woj. lubuskie
Etap rejonowy 2006-2007 klucz, GEOGRAFIA, olimpiada woj. lubuskie
Etap wojewódzki 2006-2007 arkusz, GEOGRAFIA, olimpiada woj. lubuskie
Etap szkolny 2010-2011 klucz, GEOGRAFIA, olimpiada woj. podkarpackie
Etap rejonowy 2006-2007 arkusz, GEOGRAFIA, olimpiada woj. lubuskie
Etap rejonowy 2007-2008 arkusz, GEOGRAFIA, olimpiada woj. lubuskie
Euler’s function and Euler’s Theorem, materiały do olimpiady matematycznej, zbiory zadań opracowania, ...
[ Pobierz całość w formacie PDF ]Number Theory. Tutorial 3:
Euler’s function and Euler’s Theorem
1 Euler’s
-function
Denition 1.
Let n be a positive integer. The number of positive integers
less than or equal to n that are relatively prime to n, is denoted by
(
n
)
.
This function is called Euler’s
-function or Euler’s totient function.
Let us denote Z
n
=
{
0
,
1
,
2
, . . . , n−
1
}
and by Z
n
the set of those nonzero
numbers from Z
n
that are relatively prime to
n
. Then
(
n
) is the number of
elements of Z
n
, i.e.,
(
n
) =
|
Z
n
|
.
Example 1.
Let n
= 20
. Then
Z
20
=
{
1
,
3
,
7
,
9
,
11
,
13
,
17
,
19
} and
(20) = 8
.
Lemma 1.
If n
=
p
k
, where p is prime, then
(
n
) =
p
k
−p
k−
1
=
p
k
1
−
1
p
.
Proof.
It is easy to list all integers that are less than or equal to
p
k
and
not relatively prime to
p
k
. They are
p,
2
p,
3
p, . . . , p
k−
1
· p
. We have exactly
p
k−
1
of them. Therefore
p
k
−p
k−
1
nonzero integers from Z
n
will be relatively
prime to
n
. Hence
(
n
) =
p
k
− p
k−
1
.
An important consequence of the Chinese remainder theorem is that the
function
(
n
) is multiplicative in the following sense:
Theorem 1.
Let m and n be any two relatively prime positive integers. Then
(
mn
) =
(
m
)
(
n
)
.
Proof.
Let Z
m
=
{r
1
, r
2
, . . . , r
(
m
)
}
and Z
n
=
{s
1
, s
2
, . . . , s
(
n
)
}
. By the
Chinese remainder theorem there exists a unique positive integer
N
ij
such
that 0
N
ij
< mn
and
r
i
=
N
ij
(mod
m
)
,
s
j
=
N
ij
(mod
n
)
,
1
that is
N
ij
has remainder
r
i
on dividing by
m
, and remainder
s
j
on dividing
by
n
, in particular for some integers
a
and
b
N
ij
=
am
+
r
i
,
N
ij
=
bn
+
s
j
.
(1)
As in Tutorial 2, in the proof of the Euclidean algorithm, we notice that
gcd (
N
ij
, m
) = gcd (
m, r
i
) = 1 and gcd (
N
ij
, n
) = gcd (
n, s
j
) = 1, that is
N
ij
is relatively prime to
m
and also relatively prime to
n
. Since
m
and
n
are
relatively prime,
N
ij
is relatively prime to
mn
, hence
N
ij
2
Z
mn
. Clearly,
dierent pairs (
i, j
)
6
= (
k, l
) yield dierent numbers, that is
N
ij
6
=
N
kl
for
(
i, j
)
6
= (
k, l
).
Suppose now that a number
N 6
=
N
ij
for all
i
and
j
. Then
r
=
N
(mod
m
)
,
s
=
N
(mod
n
)
,
where either
r
does not belong to Z
m
or
s
does not belong to Z
n
. Assuming
the former, we get gcd (
r, m
)
>
1. But then gcd (
N, m
) = gcd (
m, r
)
>
1 and
N
does not belong to Z
mn
. It shows that the numbers
N
ij
and only they
form Z
mn
. But there are exactly
(
m
)
(
n
) of the numbers
N
ij
, exactly as
many as the pairs (
r
i
, s
j
). Therefore
(
mn
) =
(
m
)
(
n
).
Theorem 2.
Let n be a positive integer with the prime factorisation
n
=
p
1
p
2
. . . p
r
,
where p
i
are distinct primes and
i
are positive integers. Then
1
−
1
−
(
n
) =
n
1
p
1
1
p
2
. . .
1
−
1
p
r
.
Proof.
We use Lemma 1 and Theorem 1 to compute
(
n
):
(
n
) =
(
p
1
)
(
p
2
)
. . .
(
p
r
)
1
−
=
p
1
1
−
1
p
1
p
2
1
p
2
. . . p
r
r
1
−
1
p
r
=
n
1
−
1
p
1
1
−
1
p
2
. . .
1
−
1
p
r
.
Example 2.
(264) =
(2
3
·
3
·
11) = 264
2
3
1
11
= 80
.
2
1
2
2 Congruences. Euler’s Theorem
If
a
and
b
are intgers we write
a
b
(mod
m
) and say that
a
is congruent
to
b
if
a
and
b
have the same remainder on dividing by
m
. For example,
41
80 (mod 1)3, 41
−
37 (mod 1)3, 41
6
7 (mod 1)3.
Lemma 2.
Let a and b be two integers and m is a positive integer. Then
(a) a
b
(mod
m
)
if and only if a − b is divisible by m;
(b) If a
b
(mod
m
)
and c
d
(mod
m
)
, then a
+
c
b
+
d
(mod
m
)
;
(c) If a
b
(mod
m
)
and c
d
(mod
m
)
, then ac
bd
(mod
m
)
;
(d) If a
b
(mod
m
)
and n is a positive integer, then a
n
b
n
(mod
m
)
;
(e) If ac
bc
(mod
m
)
and c is relatively prime to m, then a
b
(mod
m
)
.
Proof.
(a) By the division algorithm
a
=
q
1
m
+
r
1
,
0
r
1
< m,
and
b
=
q
2
m
+
r
2
,
0
r
2
< m.
Thus
a − b
= (
q
1
− q
2
)
m
+ (
r
1
− r
2
), where
−m < r
1
− r
2
< m
. We see that
a − b
is divisible by
m
if and only if
r
1
− r
2
is divisible by
m
but this can
happen if and only if
r
1
− r
2
= 0, i.e.,
r
1
=
r
2
.
(b) is an exercise.
(c) If
a
b
(mod
m
) and
c
d
(mod
m
), then
m|
(
a − b
) and
m|
(
c − d
),
i.e.,
a − b
=
im
and
c − d
=
jm
for some integers
i, j
. Then
ac−bd
= (
ac−bc
) + (
bc−bd
) = (
a−b
)
c
+
b
(
c−d
) =
icm
+
jbm
= (
ic
+
jb
)
m,
whence
ac
bd
(mod
m
);
(d) Follows immediately from (c)
(e) Suppose that
ac
bc
(mod
m
) and gcd (
c, m
) = 1. Then there exist
integers
u, v
such that
cu
+
mv
= 1 or
cu
1 (mod
m
). Then by (c)
a
acu
bcu
b
(mod
m
)
.
and
a
b
(mod
m
) as required.
The property in Lemma 2 (e) is called the
cancellation property
.
Theorem 3 (Fermat’s Little Theorem).
Let p be a prime. If an integer
a is not divisible by p, then a
p−
1
1 (mod
p
)
. Also a
p
a
(mod
p
)
for all a.
3
Proof.
Let
a
, be relatively prime to
p
. Consider the numbers
a
, 2
a
, ...,
(
p −
1)
a
. All of them have dierent remainders on dividing by
p
. Indeed,
suppose that for some 1
i < j
p−
1 we have
ia
ja
(mod
p
). Then
by the cancellation property
a
can be cancelled and
i
j
(mod
p
), which is
impossible. Therefore these remainders are 1, 2, ...,
p −
1 and
a ·
2
a · · · · ·
(
p −
1)
a
(
p −
1)! (mod
p
)
,
which is
(
p −
1)!
· a
p−
1
(
p −
1)! (mod
p
)
.
Since (
p −
1)! is relatively prime to
p
, by the cancellation property
a
p−
1
1 (mod
p
). When
a
is relatively prime to
p
, the last statement follows from
the rst one. If
a
is a multiple of
p
the last statement is also clear.
Theorem 4 (Euler’s Theorem).
) Let n be a positive integer. Then
a
(
n
)
1 (mod
n
)
for all a relatively prime to n.
Proof.
Let Z
n
=
{z
1
, z
2
, . . . , z
(
n
)
}
. Consider the numbers
z
1
a
,
z
2
a
, ...,
z
(
n
)
a
.
Both
z
i
and
a
are relatively prime to
n
, therefore
z
i
a
is also relatively prime
to
n
. Suppose that
r
i
=
z
i
a
(mod
n
), i.e.,
r
i
is the remainder on dividing
z
i
a
by
n
. Since gcd (
z
i
a, n
) = gcd (
r
i
, n
), yielding
r
i
2
Z
n
. These remainders
are all dierent. Indeed, suppose that
r
i
=
r
j
for some 1
i < j
n
.
Then
z
i
a
z
j
a
(mod
n
). By the cancellation property
a
can be cancelled
and we get
z
i
z
j
(mod
n
), which is impossible. Therefore the remainders
r
1
, r
2
, ..., r
(
n
)
coincide with
z
1
, z
2
, . . . , z
(
n
)
, apart from the order in which
they are listed. Thus
z
1
a · z
2
a · . . . · z
(
n
)
a
r
1
· r
2
· . . . · r
(
n
)
z
1
· z
2
· . . . · z
(
n
)
(mod
n
)
,
which is
Z · a
(
n
)
Z
(mod
n
)
,
where
Z
=
z
1
·z
2
·. . .·z
(
n
)
. Since
Z
is relatively prime to
n
it can be cancelled
and we get
a
(
n
)
1 (mod
n
).
Copyright: MathOlymp.com Ltd 2001. All rights reserved.
4
[ Pobierz całość w formacie PDF ]
