Cryptography Reference
In-Depth Information
−
√
n
for all composite
n
App.10. Prove that
φ
(
n
)
≤
n
∈
N
.
App.11. Prove that there are infinitely many
n
∈
N
such that
φ
(
n
)
>φ
(
n
+ 1).
App.12.
Suppose that
b,n
∈
N
,
p
is a prime not dividing
a
, and
g
=
gcd(
φ
(
p
b
)
,n
). Prove that
a
φ
(
p
b
)
/g
1 (mod
p
b
)
,
≡
if and only if there exists an integer
x
such that
x
n
(mod
p
b
)
.
a
≡
Exercises App.13-App.16 pertain to indices and related material. See pages
479 and 480.
App.13. Prove Proposition A.4 on page 480.
App.14. Prove that if
c
is an integer and
p
is an odd prime, not dividing
c
,
then there exists an integer
x
such that
x
2
(mod
p
)
c
≡
if and only if ind
a
(
c
) is even for any primitive root
a
modulo
p
.
App.15. Assume that
p
is an odd prime, and ord
p
(
c
) is odd. Prove that
c
x
≡−
1
(mod
p
) has no solution
x
∈
N
.
App.16. Given that
m,n
are relatively prime. Prove that
a
is a primitive
root modulo
mn
if and only if
a
is a primitive root modulo both
m
and
n
.
∈
N
be odd. Prove that the Jacobi symbol, (
n
) = 1, for all
natural numbers
m<n
with gcd(
m,n
) = 1 if and only if
n
=
a
2
for some
a
App.17. Let
n
∈
N
∈
N
. (See page 482.)
App.18. Given
a
∈
Z
. Prove that
x
2
≡
a
(mod
p
) has a solution
x
∈
Z
for all
primes
p
if and only if
a
=
b
2
for some
b
∈
Z
.
App.19. Prove that 2
x
2
219
y
2
=
−
−
1 is not solvable for any integers
x,y
.
App.20. Prove that the congruence 2
x
2
219
y
2
−
≡−
1 (mod
n
) has solutions
x,y
∈
Z
for all
n
∈
N
.
App.21. Prove that a finite integral domain is a field. (See page 483.)
App.22. Suppose that
R
is a ring, and
α
:
R
R
is an isomorphism (see pages
487-489). Then
α
is called an
automorphism
of
R
. Prove that the set of
all automorphisms of a group forms a group itself, under composition.
This group is typically denoted by
Aut
(
R
).
→
Search WWH ::
Custom Search