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 )