MathDB

Denote phi(n)=n/k , k is the greatest square with k|n

Source: Iran Third Round 1996, E2, P4

March 27, 2011

number theoryprime numbersnumber theory proposedcombinatorics

Problem Statement

Let

n

be a positive integer and suppose that

\phi(n)=\frac{n}{k}

, where

k

is the greatest perfect square such that

k \mid n

. Let

a_1,a_2,\ldots,a_n

be

n

positive integers such that

a_i=p_1^{a_1i} \cdot p_2^{a_2i} \cdots p_n^{a_ni}

, where

p_i

are prime numbers and

a_{ji}

are non-negative integers,

1 \leq i \leq n, 1 \leq j \leq n

. We know that

p_i\mid \phi(a_i)

, and if

p_i\mid \phi(a_j)

, then

p_j\mid \phi(a_i)

. Prove that there exist integers

k_1,k_2,\ldots,k_m

with

1 \leq k_1 \leq k_2 \leq \cdots \leq k_m \leq n

such that

\phi(a_{k_{1}} \cdot a_{k_{2}} \cdots a_{k_{m}})=p_1 \cdot p_2 \cdots p_n.

Back to Problems View on AoPS