You can work with Euler's Theorem, yes.

Well, we have that if then and from there when

Now if then and/or . If both divide at the same time then and the assertion is obvious since and so

So assume that only one of the prime divides , WLOG, becuase of the symmetry consider

That is: where

Then by Euler's Theorem. That is

So it all comes down to showing that iff

And this is true since by Euler's Theorem ( remember that )