with $a$ an integer such that $\gcd(a,p^k q^l)=1$ ($p,q$ two distinct prime numbers and $k,l$ integers $\ge 1$).
Is there any elementary method to solve this without using the Euler's totient function and its multiplicative properties ?
Do we have $\gcd(p,q)=1 \Rightarrow \gcd(p^k,q^l)=1$ ? All the powers of $p$ and $q$ are divided respectively by $p$ and $q$ which are different, is that enough ?
But here's a more formal proof with a weaker hypothesis ($p,q$ not necessarily prime numbers). Supposing $\gcd(p,q)=1$, so there exists $u,v\in \mathbb{Z}$ such that $up+vq=1$. Multiplying by itself it gives : $1=u^2p^2+2uvpq+v^2q^2=(u^2p+2uvq)p+v^2q^2=1\Rightarrow \gcd(p,q^2)=1$. Again, traducing the new hypothesis by Bachet-Bézout theorem and multiplying by $(up+vq=1)$ it gives that $\gcd(p,q^3)=1$. We repeat this $l-2$ times and it gives $\gcd(p,q^l)=1$.
It implies that there exists $u,v\in\mathbb{Z}$ such that $up+vq^l=1$. Multiplying by itself it gives $\gcd(p^2,q^l)=1$. This time we repeat the operation $k-1$ times and it gives $\gcd(p^k,q^l)=1$.
So now, here's an elementary proof :
First thing is to prove with an induction on $k\ge 1$ that $a^{p^{k-1}(p-1)}\equiv 1 \pmod {p^k} $.
Initialisation : for $k=1$ we found Fermat little theorem so it's true.
Heredity : for $k=k+1$ we want to prove that : $a^{p^{k}(p-1)}\equiv 1 \pmod {p^{k+1}} $.
$a^{p^{k}(p-1)}= a^{p^{k-1}p(p-1)}=(a^{p^{k-1}(p-1)})^p=(up^{k}+1)^p=\sum \limits_{l=0}^{p}\binom{p}{l}(up^k)^l=1+up^{k+1}+"..."$, where $"..."$ is divided by $p^{k+1}$. So $a^{p^{k}(p-1)}\equiv 1 \pmod {p^{k+1}} $.
We deduce the same thing for all $l\ge 1$.
Then we have : $K=a^{p^{k-1}(p-1)q^{l-1}(q-1)}= (a^{p^{k-1}(p-1)})^{q^{l-1}(q-1)}\equiv 1 \pmod{p^k}$ and also $K=a^{q^{l-1}(q-1)p^{k-1}(p-1)}=(a^{q^{l-1}(q-1)})^{p^{k-1}(p-1)}\equiv 1 \pmod{q^l}$
So now, we can say that there exists $\nu$ and $\mu$ $\in \mathbb{Z}$ such that : $K=\nu p^k +1=\mu q^l +1$
Then $\nu p^k=\mu q^l$. With the fact that $\gcd(p^k,q^l)=1$ we have by Gauss lemma $p^l$ which divides $\mu$. So there exists $\epsilon \in \mathbb{Z}$ such that $\mu=\epsilon p^k$ and finally $K=\epsilon p^kq^l+1$.
Thanks in advance !