Help on residue: $3^x + 22^y \equiv 15^z \equiv 15 \pmod{40} $

Question

I am reading this note (click here and go to page 1994 for detail, in the proof of lemma 8), and found-

$$3^x + 22^y \equiv 15^z \equiv 15 \pmod{40} $$

now, I can derive $3^x + 22^y \equiv 15^z \ \pmod{40} $ but I cann't figure out how $3^x + 22^y \equiv 15^z\pmod{40}$ is $ \equiv 15 \pmod{40}$.

How to prove that the congruence has residue 15?

Answer 1

$ \overbrace{15(15)^{\large 2n}}^{\large 15^{\:\!\LARGE 1\:\!+\,2n}\ \ }\!\bmod 40 = \color{#0a0}5(3(\!\overbrace{15)^{\large 2n}}^{\large (-1)^{\LARGE 2n}}\!\!\bmod 8) = \color{#c00}{15}\,\ $ [so $\ 15^{\large 2k}\equiv 15(\color{#c00}{15})\equiv 25\,$ for $\,k>0\,$]

using $\ \color{#0a0}ab\bmod \color{#0a0}ac = \color{#0a0}a(b\bmod c) = $ mod Distributive Law (mDL) to factor out $\,\color{#0a0}{a = 5}$

Remark $ $ The CRT argument in fleablood's comment is essentially equivalent to the above. But - as above - the mDL is much easier to apply due to its operational form. This is explained further in the linked answer (see the "Linked" questions there for many more examples). Viewed inductively, mDL reduces the induction to the above trivial induction $\ (-1)^{\large 2n} \equiv 1\ $ (compare lulu's answer here).

Answer 2

If the assumptions of your prior question hold here, then we know that $z$ is odd.

But for odd $z$, $15^z\equiv z \pmod {40}$.

To see this, We note that $15^2=225\equiv 25\pmod {40}$ and $$15^3\equiv 15\times 25\equiv 15\pmod {40}$$ Then $$15^4=15^3\times 15\equiv 15^2\equiv 25 \pmod {40}$$ and $$15^5\equiv 15^4\times 15\equiv 25\times 15\equiv 15 \pmod {40}$$ and so on.

By induction, we deduce that $15^{2n}\equiv 25\pmod {40}$ and $15^{2n+1}\equiv 15 {\pmod {40}}$.