When do $\varphi(n)=n-1$ , $\varphi(2n)=2\varphi(n)$ and $\varphi(n^k)=n^{k-1}\varphi(n)$ hold?

Proved

AlfutovaUstinov.problem_4_142

by evgeth · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

elementary-number-theoryeuler-totientnumber-theory

This is Problem 4.142 of N. B. Alfutova and A. V. Ustinov, Algebra and Number Theory (MCCME, 2002), Chapter 4, §4 “Theorems of Fermat and Euler”. The problem asks for which natural numbers $n$ the following equalities are possible, where $\varphi$ is Euler's function: (a) $\varphi(n)=n-1$ ; (b) $\varphi(2n)=2\varphi(n)$ ; (c) $\varphi(n^{k})=n^{k-1}\varphi(n)$ . The book's answers are: (a) for prime $n$ ; (b) for even $n$ ; (c) for every $n$ .

Theorem. For natural numbers $n\ge 1$ and $k\ge1$ :

$\varphi(n)=n-1$ if and only if $n$ is prime;
$\varphi(2n)=2\varphi(n)$ if and only if $n$ is even;

\varphi\!\left(n^{k}\right)=n^{k-1}\,\varphi(n)\quad\text{always holds.}

These are standard characterizations and identities for Euler's function, following from its multiplicativity and the product formula.

Formalization Note Euler's function is Nat.totient. The natural numbers $n$ (and the exponents $k$ in part 3) are assumed positive, matching the book's setting; $n-1$ and $k-1$ are natural-number subtractions, which are exact under these assumptions.

Preamble

import Mathlib

Formal statement

namespace AlfutovaUstinov

theorem problem_4_142 :
    (∀ n : ℕ, 0 < n → (Nat.totient n = n - 1 ↔ n.Prime)) ∧
      (∀ n : ℕ, 0 < n → (Nat.totient (2 * n) = 2 * Nat.totient n ↔ Even n)) ∧
      (∀ n k : ℕ, 0 < n → 0 < k → Nat.totient (n ^ k) = n ^ (k - 1) * Nat.totient n) := by sorry

end AlfutovaUstinov

Source

N. B. Alfutova, A. V. Ustinov, «Алгебра и теория чисел. Сборник задач для математических школ» (Algebra and Number Theory: a problem book for mathematical schools), Moscow: MCCME, 2002, Chapter 4 «Арифметика остатков» (Arithmetic of residues), §4 «Теоремы Ферма и Эйлера» (Theorems of Fermat and Euler), Problem 4.142. Problem text and answer as catalogued on problems.ru, problem 60768: https://problems.ru/view_problem_details_new.php?id=60768

View graph

When do φ(n)=n−1\varphi(n)=n-1φ(n)=n−1, φ(2n)=2φ(n)\varphi(2n)=2\varphi(n)φ(2n)=2φ(n) and φ(nk)=nk−1φ(n)\varphi(n^k)=n^{k-1}\varphi(n)φ(nk)=nk−1φ(n) hold?

When do $\varphi(n)=n-1$ , $\varphi(2n)=2\varphi(n)$ and $\varphi(n^k)=n^{k-1}\varphi(n)$ hold?