MHB Introductory number theory challenge

AI Thread Summary
The discussion revolves around proving that if \( n = pq \) where \( p \) and \( q \) are distinct primes, and \( a \) is coprime to \( n \), then \( a^{p^k + q^k} \equiv a^{n^k + 1} \pmod{n} \) for all integers \( k \). The proof utilizes induction and Euler's Theorem, starting with the base case for \( k = 1 \) and assuming the statement holds for \( k \) to prove it for \( k + 1 \). A participant raised a concern regarding the validity of the proof's assumptions, prompting clarification that the implication from the modular equivalence is sufficient. The discussion concludes with acknowledgment that the condition of \( \gcd(a, n) = 1 \) is not necessary for the proof. The overall conclusion is that the statement holds true under the given conditions.
Nono713
Gold Member
MHB
Messages
615
Reaction score
4
Let $n = pq$ such that $p$ and $q$ are distinct primes. Let $a$ be coprime to $n$. Show that the following holds:

$$a^{p^k + q^k} \equiv a^{n^k + 1} \pmod{n} ~ ~ ~ ~ ~ \text{for all} ~ ~ k \in \mathbb{Z}$$
 
Last edited:
Mathematics news on Phys.org
One possible proof is by induction. First, we use Euler's Theorem to simplify the statement:

$$a^{p^k + q^k} \equiv a^{n^k + 1} \pmod{n} ~ ~ ~ \Longleftrightarrow ~ ~ ~ p^k + q^k \equiv n^k + 1 \pmod{\varphi{(n)}}$$

Now, we show that the base case $k = 1$ is true.

$$p + q \equiv n + 1 \pmod{\varphi{(n)}}$$

And as $\varphi{(n)} = (p - 1)(q - 1)$, this is true (add $\varphi{(n)}$ to the left hand side).

Now, assume the statement holds for all exponents between $1$ and $k$ inclusive. Then we know that:

$$p^k + q^k \equiv n^k + 1 \pmod{\varphi{(n)}}$$

$$p + q \equiv n + 1 \pmod{\varphi{(n)}}$$

And so we obtain:

$$(p^k + q^k)(p + q) \equiv (n^k + 1)(n + 1) \pmod{\varphi{(n)}}$$

$$p^{k + 1} + q^{k + 1} + q p^k + p q^k \equiv n^{k + 1} + 1 + n^k + n \pmod{\varphi{(n)}}$$

So we see that if the statement is to hold true for $k + 1$, we just need to show that:

$$q p^k + p q^k \equiv n^k + n \pmod{\varphi{(n)}}$$

Divide this through by $n$, which is valid as $\gcd{(n, \varphi{(n)})} = 1$, thus:

$$p^{k - 1} + q^{k - 1} \equiv n^{k - 1} + 1 \pmod{\varphi{(n)}}$$

Which is the statement for $k - 1$, true by assumption! So it also holds for $k + 1$, and by induction holds for all $k > 0$.

Now consider the case $k < 0$. For this step, note that:

$$\left ( p^k + q^k \right ) \cdot n^{-1} \equiv \left ( n^k + 1 \right ) \cdot n^{-1} \pmod{\varphi{(n)}} ~ ~ ~ \Longleftrightarrow ~ ~ ~ q^{-k} p^0 + p^{-k} q^0 \equiv n^0 + n^{-k} \pmod{\varphi{(n)}}$$

$$\therefore ~ ~ p^{-k} + q^{-k} \equiv n^{-k} + 1 \pmod{\varphi{(n)}}$$

Showing that if the statement holds for $k$, then it also holds for $-k$. Finally, show the trivial case $k = 0$.

$$\blacksquare$$

Interestingly, this has a connection to the pairs $(x, y)$ which satisfy the following equivalence:

$$x^k + y^k \equiv n^k + 1 \pmod{\varphi{(n)}} ~ ~ ~ \Longleftrightarrow ~ ~ ~ \left ( x + y \right )^k \equiv \left ( n + 1 \right )^k \pmod{\varphi{(n)}} ~ ~ ~ ~ ~ \text{for all} ~ ~ k \in \mathbb{Z}$$

For which any solution $(x, y)$ must be some linear combination of $p$, $q$ and $n - 1$.

Note that the exponent space is not really $\mathbb{Z}$ but $\mathbb{Z} / \varphi{(\varphi{(n)})} \mathbb{Z}$.
 
Bacterius said:
Let $n = pq$ such that $p$ and $q$ are distinct primes. Let $a$ be coprime to $n$. Show that the following holds:

$$a^{p^k + q^k} \equiv a^{n^k + 1} \pmod{n} ~ ~ ~ ~ ~ \text{for all} ~ ~ k \in \mathbb{Z}$$
Since $a^p\equiv a \pmod{p}$, we have $a^{p^k}\equiv a \pmod{p}$.
Now, $a^{p^k+q^k}\equiv a^{p^k}a^{q^k}\equiv a^{q^k+1}\pmod{p}$
And, $a^{n^k+1}=a^{p^kq^k+1}\equiv(a^{p^k})^{q^k}a \equiv a^{q^k+1}\pmod{p}$

Thus, $a^{p^k+q^k}\equiv a^{n^k+1}\pmod{p}$.
Similarly, $a^{p^k+q^k}\equiv a^{n^k+1}\pmod{q}$.
From the above two we have, $a^{p^k+q^k}\equiv a^{n^k+1}\pmod{pq}$.

Hence $a^{p^k+q^k}\equiv a^{n^k+1}\pmod{n}$.
 
Bacterius said:
One possible proof is by induction. First, we use Euler's Theorem to simplify the statement:

$$a^{p^k + q^k} \equiv a^{n^k + 1} \pmod{n} ~ ~ ~ \Longleftrightarrow ~ ~ ~ p^k + q^k \equiv n^k + 1 \pmod{\varphi{(n)}}$$

Hello Bacterius.

I don't see how the above is true.
Are you using that $a^i\equiv a^j \pmod{n}\Rightarrow i\equiv j\pmod{n}$.

If yes then I think the solution is incorrect as $4^3\equiv 4\pmod{15}$ but $3\not\equiv 1\pmod{\varphi(15)}$.

If no then please explain it in little more detail.
 
You are correct, I went a bit too fast here. The arrow only goes in one direction:

$$p^k + q^k \equiv n^k + 1 \pmod{\varphi{(n)}} ~ ~ ~ \implies ~ ~ ~ a^{p^k + q^k} \equiv a^{n^k + 1} \pmod{n}$$

This implication should remain strong enough for the proof. Sorry about that.
 
Bacterius said:
You are correct, I went a bit too fast here. The arrow only goes in one direction:

$$p^k + q^k \equiv n^k + 1 \pmod{\varphi{(n)}} ~ ~ ~ \implies ~ ~ ~ a^{p^k + q^k} \equiv a^{n^k + 1} \pmod{n}$$

This implication should remain strong enough for the proof. Sorry about that.
Okay then. Also my proof in post#3 suggests that we don't even need $gcd(a,n)=1$. Isn't it?
 
What the hell. I am tired today, I didn't even see your third post. Yes, that condition is not required either, I added it just to make sure because I wasn't yet sure myself when I posted the problem. Your proof is correct and a nice approach of dividing the problem mod p and mod q. (Yes)
 
Bacterius said:
What the hell. I am tired today, I didn't even see your third post. Yes, that condition is not required either, I added it just to make sure because I wasn't yet sure myself when I posted the problem. Your proof is correct and a nice approach of dividing the problem mod p and mod q. (Yes)
Thanks. :)
 

Similar threads

Back
Top