It's fairly standard procedure to break down moduli into prime powers; for example we might do this in order to later apply the Chinese Remainder Theorem.
So let and prove that in both cases we get the desired result.
Then gcd(a,9)=1 and by Euler's theorem since eulerphi(9)=6.
Now either or . In the former case, we have . In the latter case we have gcd(a,7)=1 and eulerphi(7)=6 so as before .
Therefore in this case