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)...
- 116
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^...
- 5,607
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 ...
- 6,626
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 ...
- 118k
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 ...
- 1,864
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 ...
- 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\...
- 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+\...
- 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$ ...
- 15.5k
Only top scored, non community-wiki answers of a minimum length are eligible