MathDB
Phi function and its conjugate

Source: 2022 3rd OMpD L3 P1 - Brazil - Olimpíada Matemáticos por Diversão

July 8, 2023
phi functionprime factorizationnumber theoryfunction

Problem Statement

Given a positive integer n≥2n \geq 2, whose canonical prime factorization is n=p1α1p2α2…pkαkn = p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}, we define the following functions: φ(n)=n(1−1p1)(1−1p2)…(1−1pk);φ‾(n)=n(1+1p1)(1+1p2)…(1+1pk)\varphi(n) = n\bigg(1 -\frac{1}{p_1}\bigg) \bigg(1 -\frac{1}{p_2}\bigg) \ldots \bigg(1 -\frac {1}{p_k}\bigg) ; \overline{\varphi}(n) = n\bigg(1 +\frac{1}{p_1}\bigg) \bigg(1 +\frac{1}{p_2}\bigg) \ldots \bigg(1 + \frac{1}{p_k}\bigg) Consider all positive integers nn such that φ‾(n)\overline{\varphi}(n) is a multiple of n+φ(n)n + \varphi(n) . (a) Prove that nn is even. (b) Determine all positive integers nn that satisfy this property.
Back to ProblemsView on AoPS