You should try using the Chinese Remainder Theorem.
It will suffice to show that and simultaneously. Keep in mind that .
Note that here , and therefore .
Euler's Theorem implies that ; also is even since . Hence . In a similar way, we have the congruence .
By hypothesis , so we can merge the main congruences to one that is equivalent, namely . But , so .