6 votes
Accepted

What are phi and tau defined as?

$\phi(n)$ is the number of positive integers less or equal to $n$ that are relatively prime to $n$. For example, $\phi(5)=4$ since $\{1,2,3,4\}$ are all relatively prime to $5$. The function $\tau(n)...
user avatar
5 votes
Accepted

Showing $\phi(n^2) = n\, \phi(n)$

$\begin{align}\frac{\varphi(n^2)}{n^2}&=\Pi_{p|n^2} (1-\frac{1}{p})\\&=\Pi_{p|n} (1-\frac{1}{p}) \\&=\frac{\varphi(n) }{n}\end{align} $ Note : $p|n^2=n\cdot n$ implies $p|n$ . Hence $p|n^...
user avatar
4 votes
Accepted

How to read m $\bot$ n in totient function?

The only meaning that makes sense is that $m\bot n\iff \gcd(m.n) = 1$. Though I must admit that I never saw this notation before, and without the context I wouldn't have guessed what it's supposed to ...
user avatar
3 votes
Accepted

Show that there are infinitely many positive integers $n$ for which $\phi(n)^2 + n^2$ is a perfect square.

Let $n=3^k\cdot 5$ for $k\ge 1$. Then we have $\phi(n)=8\cdot 3^{k-1}$, and hence $$ n^2+\phi(n)^2=3^{2k}\cdot 5^2+8^2\cdot 3^{2k-2}=(3^{k-1})^2(9\cdot 5^2+8^2)=(17\cdot 3^{k-1})^2. $$ This holds for ...
user avatar
2 votes

What are phi and tau defined as?

$\phi(n)$, known as Euler's totient function or phi function given the number of positive integers not exceeding $n$ and relatively prime to $n$. For example, $\phi(6)=2$ because $1$ and $5$ are the ...
user avatar
1 vote
Accepted

Why need of totient function to find generators of cyclic group $C_n$?

First, I am your downvoter. You keep biting off more than you can chew. It's quite a mess. However, here's one more college try: A basic fact about cyclic groups, which it would be great progress ...
user avatar
  • 623
1 vote
Accepted

Euler's Theorem Application

First find the order of $49 \mod 155$. It is a divisor of $\varphi(155) = 120$. By trying (using repeated squaring) we find $49^{30} \equiv 1$ but $49^{15} \equiv 94 \not\equiv 1$, $49^{10} \equiv 36\...
user avatar
  • 6,934
1 vote

Different approach to $\lim_{n \rightarrow \infty} \phi(n)$

I think what you need is the following fact: Lemma: Let $f(n)$ be a positive multiplicative function. If $f(q)\to+\infty$ as prime power $q\to\infty$. Then $f(n)\to+\infty$ as positive integer $n\to+\...
user avatar
  • 3,777
1 vote
Accepted

Is there a combinatorial proof that Euler's totient function divides Jordan's totient function?

Equivalently, $J_k(n)$ counts the $k$-tuples $(a_1,\cdots,a_k)$ of elements of $\mathbb{Z}/n\mathbb{Z}$ which generate the whole ring (as an ideal). We can verify $(\mathbb{Z}/n\mathbb{Z})^\times$ ...
user avatar
  • 15.5k

Only top scored, non community-wiki answers of a minimum length are eligible