Let $\phi(x)=m$, where $\phi(x)$ is Euler’s phi function, And $x=\prod_{i=1}^{n}p_i^{a_i}$ Thus: $$\phi(x)=\phi\left(\prod_{i=1}^{n}p_i^{a_i}\right)= \prod_{i=1}^{n}p_i^{a_i}-p_i^{a_i-1} =m$$ $$\iff m= \prod_{i=1}^{n}p_i^{a_i-1}\left(p_i-1\right) $$ Now let $d_i=p_i-1$: $$m =\prod_{i=1}^{n}p_i^{a_i-1}d_i= \prod_{i=1}^{n}\frac{p_i^{a_i}}{p_i}d_i= \prod_{i=1}^{n}p_i^{a_i}\frac{d_i}{p_i} $$ $$\iff m=x \prod_{i=1}^{n} \frac{d_i}{p_i} \iff x= \frac{m}{\prod_{i=1}^{n}d_i}\prod_{i=1}^{n}p_i$$ I think that this is the solution to the equation $\phi(x)=m$, but how can i use this result to solve it?
122066
I am having trouble with understading how inverse totient function works. I know it can have multiple solutions but I don't understand how to find all of them for bigger numbers. For example how would one approach to problem of solving this equation:  ϕ(n) = 180  I do understand that one should represent ϕ(n) by product rule and somehow conclude numbers by combining product rule expression for ϕ(n) to get all numbers n. But it seems as very long process that I don't understand. My question is how I should think when looking at prime numbers expression for ϕ(n) and how should I eliminate some results? I was trying searching other similiar question and I still can't find some general algorithm for solving this problem.  Thanks!  EDIT: I would like to know how to calculate this problem by hand
51027
Given $m\in\mathbb{N}$, is there a general way to solve the equation \begin{equation} \varphi(n)=m \end{equation} where $\varphi$ is the Euler's totient function? For example, I want to solve for all the $n$'s such that $\varphi(n)=4$. Is there any way to solve it that are also applicable to many (if not general) cases?
113982
I can't figure this problem out.  Let $b_1, b_2, \cdots, b_{\phi(m)}$ be the integers between $1$ and $m$ that are relatively prime to $m$. $B$ is the product of these integers. Prove that either $B$ is congruent to $1$ or $B$ is congruent to $-1 \pmod{m}$. Could you give me some hint where to start?  EDIT: Please avoid use of group theory. I am an undergrad in my first semester of number theory.
63336
$a$ and $m$ are natural numbers and $a&gt;1$. Prove that $m | \phi(a^m -  1)$.   Any hints how can I prove this statement?
94109
I know that the way to calculate Euler Totients of a number X is to take the prime factorization of X and then use the rule $φ(p^n) = p^n - p^{n-1}$ on each of those prime factorizations and multiply all of the results together. My question is why do these hold true. First, what allows you to say that $φ(A \cdot B) = φ(A) \cdot φ(B)$ and also why $φ(p^n) = p^n - p^{n-1}$.
74422
How do I generalize the equation to be able to plug in any result for $\phi(n)=12$ and find any possible integer that works?
91012
I noticed that $f(x) = x\phi(x)$ seems to be one-to-one, where $\phi(x)$ is Euler's Phi function.  In particular, I'm writing some numerical python code and the line I have looks something like  sorted([n*phi(n) for n in range(1,1000)])   and there are no duplicates in the list.  First, is it one-to-one?  Second, if it is, is there a simple proof sketch?
116134
I'm trying work on problem 11 of Chapter 3 in Ireland and Rosen's Number Theory.   Suppose $\{a_1,\dots,a_{\phi(n)}\}$ is a reduced residue system modulo $n$. Let $N$ be the number of solutions to $x^2\equiv 1\pmod{n}$, then $$ a_1\cdots a_{\phi(n)}\equiv (-1)^{N/2}\pmod{n}. $$  How can this be shown? I know that if $n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$, then $N=\prod N(p_i^{\alpha_i})$ where $N(p_i^{\alpha_i})$ denotes the number of solutions to $x^2\equiv 1\pmod{p_i^{\alpha_i}}$.   Also, if $x_0$ is a solution, then it is also a solution to $x^2\equiv 1\pmod{p_i}$ for any prime in the factorization of $n$. This implies that $x_0\equiv \pm 1\pmod{p_i}$, so that $x_0$ is coprime to all prime factors of $n$, and thus coprime to $n$.  But I'm not seeing a connection between the left and right hand side products of the congruence in question. Thanks.
38398
I am a bit confused by the concepts of . In all the courses I am doing at the moment we do transformations of the form: $$ \phi(x) \rightarrow\phi'(x') = \phi(x) $$ and $$ \partial_{\mu}\phi(x)\rightarrow\partial' _{\nu}\phi(x') = \frac{\partial x^{\alpha}}{\partial x' ^{\nu}}\partial_{\alpha}\phi(x) $$ This is all perfectly clear to me. However, I am reading Peskin and Schoder at the moment, and they adapt an "active" point of view (their words), such that the above transformations are: $$ \phi(x) \rightarrow\phi'(x) = \phi(\Lambda^{-1}x) $$ and $$ \partial_{\mu}\phi(x)\rightarrow\partial _{\mu}(\phi(\Lambda^{-1}x)) = (\Lambda^{-1})^{\nu}_{\mu}(\partial_{\nu}\phi)(\Lambda^{-1}x). $$ I don't understand how to interpret this and especially how to derive the second equation.
8673
From A Classical Introduction to Modern Number Theory by Ireland and Rosen, page 33:     Corollary 1 (Euler's Theorem). If $(a,m) = 1$, then $a^{\phi(m)} \equiv 1\,(m)$.      Proof. The units in $\mathbb{Z}/m\mathbb{Z}$ form a group of order $\phi(m)$. If $(a,m) = 1$, $\bar{a}$ is a unit. Thus $\bar{a}^{\phi(m)} = \bar{1}$ or $a^{\phi(m)} \equiv 1\,(m)$.   If I'm interpreting this correctly, this proof implicitly uses the fact(?) that if $G$ is a group and $x\in G$, then $x^{|G|}=1$, where $1$ is the identity element of $G$.  If this is indeed true, can someone explain why? (I have had no prior exposure to group theory.)
18891
The constraints are   $0 \le a_1,a_2....a_n,b_1,b_2....b_n \le 1$. $|a_i-b_i|&lt; \delta$ for all $1 \le i \le n $   How do I go about proving the following $$|\prod_{i=1}^n a_i-\prod_{i=1}^n b_i| &lt; n\delta$$  I tried reducing it to two terms where one term is like $(a-\delta)^n$ so that I can get the $n\delta$ term from binomial,but I am stuck. I would really appreciate just hints.
31668
Let $P_n, P_m$ be Legendre polynomials with $n \neq m$ then: $$\int_{-1}^1 P'_m(x) P'_n (x) (1-x^2) dx=0$$  I already know that $\int_{-1}^1 P_m (x) P_n (x) dx=0$, using that $P_n$ and $P_m$ are solutions of Legendre equation then:  $$ [(1-x^2)P'_n]' +n (n+1)P_n=0 $$ $$ [(1-x^2)P'_m]' +m (m+1)P_m=0 $$  Then if we integrate $(Equation 1)P_m - (Equation 2)P_n$ we obtain:   $$\int_{-1}^{1} P_m[(1-x^2)P'_n]' - P_n [(1-x^2)P'_m]' dx + [n (n+1) - m (m+1)]\int_{-1}^1 P_n P_m dx =0 $$  If we use integration by parts we obtain that the first integral is $0$, then $\int_{-1}^1 P_m(x) P_n (x) dx=0$  I want to use a similar method to prove that $\int_{-1}^1 P'_m(x) P'_n (x) (1-x^2) dx=0$ but I don't know where to start.
81669
If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$.   I have no idea to solve this question. Please help me to solve the problem.
61810
How can I show that the order of an element modulo $n$ divides $\phi(n)$?  I know that if $a$ and $n$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod n$ is its order modulo $n$. I also know that, by Euler's theorem, $a^{\phi(n)}\equiv1\pmod n$. Therefore, it must be the case that $x\leq\phi(n)$.  However, all that I am left to do is to show that $kx=\phi(n)$, for some integer $k$. Do you guys have an idea on how to do this? Thanks in advance!
63331
So I know that if $(a,n)=1$, then $a^{\phi(n)}≡1\pmod{n}$ by Euler's Theorem. I also know that $d \mid a^k$ and obviously $d \mid n$. I know I probably need to use this in the proof, but I just don't know how to get started.
85137
Let $p_n$ denote the $n$'th prime number.  How would one go about proving that infinite products like: $$\prod_{k=1}^\infty1 - \frac{1}{(p_k)^2} = \frac{6}{\pi^2}$$  or  $$\prod_{k=1}^\infty\frac{{p_k}^2}{{p_k}^2 - 1} = \frac{\pi^2}{6}$$ are correct?  Is there any way to prove it except by exhaustion?
109287
For a polynomial $f=X^n+a_1X^{n-1}+\ldots+a_n \in \mathbb{Q}[X]$ we define $\varphi(f):=a_1 \in \mathbb{Q}$. Now I want to show that for the $n$th cyclotomic polynomial $\Phi_n$ it holds that $$\varphi(\Phi_n)=-\mu(n)$$ where $\mu(n)$ is the Möbius function. What I know is that $\displaystyle\Phi_n=\prod_{d|n} (X^{\frac{n}{d}}-1)^{\mu(d)}$.