# Euler's totient function counts

Let $n$ be a positive integers. Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as $\phi(n)$. Put $$A=\begin{bmatrix}‎ ‎1&0&0&\cdots & 1\\‎ ‎1&1&0&\cdots & 2\\‎ 1&0&1&\cdots & 3\\‎ ‎\vdots&\vdots&\ddots&\vdots&\vdots\\‎ ‎‎\end{bmatrix}$$ $A$ is the $n\times n$ matrix where the last columns of matrix $A$ are the numbers $1,2,3,\ldots$ and the others entries of the columns $A=(a_{i,p})$ where $1\leq i,p \leq n$ is defined as following $$‎a_{i,p} = \begin{cases} 1, & \text{if } p\mid i,\\ 0, & \text{if } p\nmid i. \end{cases}$$ Proved that $\phi(n)=\mid A\mid$.

• What's $p$? When do you think $i\nmid i$? – B. Goddard Jan 12 '18 at 17:41
• What is your question exactly? What have you tried so far? – Florian Jan 12 '18 at 19:05
• @Florian I closed to prove it! By using multiplicative of ϕ(n) it is enough to prove for ‎$‎n=p^k‎$‎. The entry of ‎rows ‎‎$‎p^{k−1}‎$‎ and ‎$‎p^k‎$‎ are equal but the entries ‎$‎a_{p^{k-1},n}‎‎=p^{k−1}‎$‎ and ‎$‎a_{p^k,n}‎‎=p^k‎$‎.So by subtracting these two rows we have $\phi(p^k)=p^k-p^{k-1}$ – d.y Jan 12 '18 at 21:36