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.\]
Problem
Source: Iran Third Round 1996, E2, P4
Tags: number theory, prime numbers, number theory proposed, combinatorics
grupyorum
22.08.2019 19:23
This is an extremely beautiful problem, mix of linear algebra and combinatorics! Here is a solution, one step missing. I hope someone can fill it in. Note that, if $q_1<\cdots<q_N$ are primes, then $$ n=\prod_{j=1}^N q_j^{\beta_j}\implies \phi(n)= \prod_{j:\beta_j\equiv 1\pmod{2}}q_j. $$Now, note that, $p_i\mid \phi(a_i)\Leftrightarrow a_{i,i}\equiv 1\pmod{2}$. Moreover, the condition $p_i \mid \phi(a_j)\Leftrightarrow p_j\mid \phi(a_i)$ implies also that, $a_{i,j}\equiv a_{j,i}\pmod{2}$. Now, motivated by this, construct a matrix $A\in\{0,1\}^{n\times n}$ with entries $A_{ij}\equiv a_{ij}\pmod{2}$. In particular, from the given construction, it holds that $A$ is a symmetric binary matrix, with diagonal entries all ones. Therefore, the question boils down establishing the existence of a vector $v\in\{0,1\}^n$, such that $Av$ is a vector of all ones, where the arithmetic is done modulo $2$ from now on. Consider the set, $\{Av:v\in\{0,1\}^n\}$, which can take at most $2^n$ different values. Assume that, there exists two vectors $v_1,v_2$ such that $Av_1=Av_2$ (entry wise), with $v_1\neq v_2$. Then, $Av=0$ for some vector $v$ This is the missing step: Assume $\sum_i v_i=1$. Now, under that assumption, let us inspect $v^T Av = \sum_{i,j} v_iv_jA_{ij}$. On one hand, $Av=0$ implies this object is zero. On the other hand, we have $v^T Av=\sum_i v_i^2 A_{ii}+\sum_{i<j}v_iv_j(A_{ij}+A_{ji})\equiv \sum_i v_i\pmod{2}$, using the facts: $A_{ij}\equiv A_{ji}\pmod{2}$, $A_{ii}\equiv 1\pmod{2}$, $v_i^2\equiv v_i\pmod{2}$. Therefore, $\sum_i v_i =1$, which contradicts with the early assumption. Other link.