Two Not So Quick Questions

**Aryth** · May 6th 2009, 06:57 AM

I've been wondering if there are proofs for these two questions... Searching has given me nothing. These aren't new results so they SHOULD be out there, but I can't find them.

1. Let p and q be distinct primes. Prove that, for any $a \in \mathbb{Z}$

$a^{pq} \equiv a^p + a^q (mod \ pq)$

2. Let $a < m$ be two positive integers. Prove that a and m are relatively prime if and only if there is some power of a which is an inverse of a modulo m.

**NonCommAlg** · May 6th 2009, 07:04 AM

Originally Posted by Aryth

I've been wondering if there are proofs for these two questions... Searching has given me nothing. These aren't new results so they SHOULD be out there, but I can't find them.

1. Let p and q be distinct primes. Prove that, for any $a \in \mathbb{Z}$

$a^{pq} \equiv a^p + a^q (mod \ pq)$

this is false! check the question again!

**NonCommAlg** · May 6th 2009, 07:16 AM

Originally Posted by Aryth

2. Let $a < m$ be two positive integers. Prove that a and m are relatively prime if and only if there is some power of a which is an inverse of a modulo m.

the "if" part: if $a^k \equiv a^{-1} \mod m,$ then $a^{k+1} \equiv 1 \mod m.$ now it's clear that $a,m$ cannot have any common divisor greater than 1.

for the "only if" part use this fact that if $\gcd(a,m)=1,$ then $a^{\varphi (m)} \equiv 1 \mod m$ and thus $a^{\varphi(m)-1} \equiv a^{-1} \mod m.$

**Aryth** · May 6th 2009, 08:07 AM

Originally Posted by NonCommAlg

this is false! check the question again!

You're right... I missed a part:

$a^{pq} + a \equiv a^p + a^q (mod \ pq)$

**NonCommAlg** · May 6th 2009, 08:31 AM

Originally Posted by Aryth

You're right... I missed a part:

$a^{pq} + a \equiv a^p + a^q (mod \ pq)$

since $x-y \mid x^n - y^n,$ for any positive integer $n,$ we have $q \mid a^q - a \mid a^{pq} - a^p$ and $p \mid a^p - a \mid a^{pq}-a^q.$ thus $q \mid a^{pq} - a^p$ and $p \mid a^{pq} - a^q.$ thus:

$q \mid a^{pq}-a^p - (a^q - a)$ and $p \mid a^{pq}-a^q - (a^p -a).$ but $a^{pq}-a^p - (a^q - a)= a^{pq}-a^q - (a^p -a).$ thus: $pq \mid a^{pq}-a^p - a^q + a,$ and we're done.

**Aryth** · May 6th 2009, 12:26 PM

Thanks for the help. I really appreciate it.

Thread: Two Not So Quick Questions

LinkBack

Thread Tools

Display

Two Not So Quick Questions

Similar Math Help Forum Discussions

Two quick questions.

two quick questions

Some quick questions

PLEASE HELP! 2 quick questions! thanks!

3 Quick Questions

Search Tags