Solving , and
ProvedAlfutovaUstinov.problem_4_141diophantine-equationselementary-number-theoryeuler-totientnumber-theory
This is Problem 4.141 of N. B. Alfutova and A. V. Ustinov, Algebra and Number Theory (MCCME, 2002), Chapter 4, §4 “Theorems of Fermat and Euler”. Here is Euler's function. The problem asks to solve, in natural numbers , the equations (a) ; (b) ; (c) . The book's answers: (a) ; (b) with ; (c) no solutions.
Theorem. For natural numbers :
- if and only if for some integer ;
- if and only if for some integers , ;
The problem illustrates the product formula : the ratio depends only on the set of prime divisors of .
Formalization Note Euler's function is Nat.totient. Each equation is written without division as , which is equivalent for natural numbers; the solution sets are stated as equalities of subsets of , restricted to .
Preamble
import Mathlib
Formal statement
namespace AlfutovaUstinov
theorem problem_4_141 :
{x : ℕ | 0 < x ∧ 2 * Nat.totient x = x} = {x | ∃ α : ℕ, 0 < α ∧ x = 2 ^ α} ∧
{x : ℕ | 0 < x ∧ 3 * Nat.totient x = x} =
{x | ∃ α β : ℕ, 0 < α ∧ 0 < β ∧ x = 2 ^ α * 3 ^ β} ∧
{x : ℕ | 0 < x ∧ 4 * Nat.totient x = x} = ∅ := by sorry
end AlfutovaUstinovSource
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.141. Problem text and answer as catalogued on problems.ru, problem 60767: https://problems.ru/view_problem_details_new.php?id=60767