Let
,
, and let
with
. Prove that if
and
are not relatively prime, then there exists an integer
with
such that
. Deduce that there cannot exist an integer
such that
.
Suppose
. Then we have
for some
, and
. Moreover
for some
, so that, mod n, we have
.
Suppose now that
mod n for some
. Then we have, mod n,
. But then
, a contradiction. So no such
exists.
Suppose
Suppose now that
No comments:
Post a Comment