Introductory number theory challenge

[Bacterius]

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}$$

 

[Bacterius]

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}$.

 

[caffeinemachine]

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}$.

 

[caffeinemachine]

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.

 

[Bacterius]

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.

 

[caffeinemachine]

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?

 

[Bacterius]

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.

 

[caffeinemachine]

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.

Thanks.