Euler's totient function counts the integers in a complete complete residue system that are coprime to the modulus:
If the prime factorization is with distinct prime numbers , Euler's totient product formula is
In particular, . Adjoining the prime factor changes neither the odd factor nor its count of units, since . The product formula gives
This is a positive integer distinct from , as required.