show that if an integer n has at least two distinct odd prime divisors then there exists k<φ(n) such that
a^k ≡ 1(mod n)for every a relatively prime to n.
What I have so far: The expression a^k ≡ 1(mod n) looks similar to Euler's Generalization of Fermat's Little Theorem. Also, n can be expressed as xp1p2, where x is a positive integer, and p1 and p2 are odd distinct prime numbers.
I know this isn't much, but I don't to where to go afterwards to complete the proof.
Originally Posted by ilikecandy
show that if an integer n has at least two distinct odd prime divisors then there existssuch that
for every a relatively prime to n.
What I have so far: The expression a^k ≡ 1(mod n) looks similar to Euler's Generalization of Fermat's Little Theorem. Also, n can be expressed as xp1p2, where x is a positive integer, and p1 and p2 are odd distinct prime numbers.
I know this isn't much, but I don't to where to go afterwards to complete the proof.: suppose
and
if
and
then
now letwhere
are some odd primes and
let
where
is the Euler's totient function.
letand suppose
by
we also have
so, again by
we get:
Remark: i suggest you read about the Carmichaelfunction a little bit to learn about the minimum value of that
in your problem.
  |
LinkBack URL
About LinkBacks