Final answer:
An integer n is prime if and only if its Euler φ-function φ(n) = n −1. The proof is done in two parts: if n is prime, then φ(n) = n −1; and if φ(n) = n −1, then n is prime.
Step-by-step explanation:
In order to prove that an integer n is prime if and only if its Euler φ-function φ(n) = n −1, we need to show two parts: if n is prime, then φ(n) = n −1; and if φ(n) = n −1, then n is prime.
Part 1: If n is prime, then φ(n) = n −1. When n is prime, all positive integers less than n are coprime to n. Therefore, the Euler φ-function φ(n) counts how many positive integers less than n are coprime to n, which is n-1.
Part 2: If φ(n) = n −1, then n is prime. If φ(n) = n −1, it means that there are n-1 positive integers less than n that are coprime to n. Therefore, n must be prime because if n had a divisor greater than 1 and less than n, the φ-function value would be less than n-1.