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?
5065
Let $\phi(n) $ is the numbers of number that are relatively prime to n.   Then, how could we solve the equation $\phi(n) = k, k &gt; 0?$   For example:    $\phi(n) = 8 $  I can use computer program to check all numbers that are relatively prime to $n$, but I think there must be an easier way to approach this problem.    Base on this formula: $$\prod_{i=0}^{k} p_{i}a^{a_i} $$ The only thing I can see is n must not have a prime factor > 9, otherwise $\phi(n) &gt; 8 $. I really don't know where to start :( ? A hint would be greatly appreciated.
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.
71321
I have this homework problem assigned and I'm a little confused in solving it:  Find all solutions of $\phi(n)=16$ and $\phi(n)=24$ (where $\phi(n)$ is the Euler phi-function).  The hint that's provided says:  If $n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$ satisfies $\phi(n)=k$, then $n=\frac{k}{\prod (p_i-1)}\prod p_i$. Thus the integers $d_i=p_i-1$ can be determined by the conditions (1) $d_i\mid k$, (2) $d_i+1$ is prime, and (3) $\frac{k}{\prod d_i}$ contains no prime factor not in $\prod p_i$.  I'm ok with proving the statements in the hint and I know how to get them, but I'm not sure how to apply them 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!
58309
I am asked to find all positive integers $n$ such that $\phi(n)=6$, and to prove that I have found all solutions.  The way I am tackling this is by constructing all combinations of prime powers such that when passed to Euler's function will yield $6$.  For example, I know that $\phi(7)=6$, $\phi(3^2)=6$, and $\phi(2)=1$. Therefore, the numbers should be $7$, $7\cdot2=14$, $3^2=9$, and $3^2\cdot2=18$.  I believe that there cannot possibly be any others because of the way the $\phi$ function is defined. What do you guys think?
32207
The only solution that I have been able to come up with is $d=1$, but because $d&gt;2$, I can't seem to figure out how to find a solution.
17890
I saw the answer to  and it is the same problem, but i didn't get how to use the tip S.C.B gave. This was the tip: $"$First, assume that it is not $a$ primitive root $(\text{mod m})$. Then we have that there exists such $r&lt;\phi(m)$ such that $$a^r\equiv 1(\text{mod m})$$ Now use that, if $n=mk$ $$ϕ(mk)=ϕ(m)ϕ(k)\frac{d}{ϕ(d)}≥ϕ(m)ϕ(k)&gt;rϕ(k)$$ where $d=gcd(m,k)"$ and i saw the answer to this question using group theory, but i want an answer using elementary number theory, if you have a different answer, or tip, it would be good as well. What i tried was this: $n=mk$, then $$a^{\phi(n)}\equiv 1(\text{mod n})\Rightarrow a^{\phi(mk)}\equiv1(\text{mod mk}) \Rightarrow a^{\phi(mk)}\equiv1(\text{mod m})$$ But i don't know how to follow from here
12660
How do we prove that $\dfrac{\phi^{400}+1}{\phi^{200}}$ is an integer, where $\phi$ is the golden ratio?  This appeared in an answer to a  I asked previously, but I do not see how to prove this..
107875
My idea for the solution is something like this:  Since $2 | n$, $n = 2^a p_1^{e1} p_2^{e2} \cdots p_t^{et}$ where $a \geq 1$.  Then, $n/2 = \phi(2^a) \phi(p_1^{e1}) \phi(p_2^{e2}) \cdots \phi(p_t^{et})$.  Looking at the case that $t = 0$,  $n/2 = \phi(2^a) = 2^{a-1}$, and therefore $n = 2^a$.  Otherwise, $n = 2^a \phi(p_1^{e1}) \phi(p_2^{e2}) \cdots \phi(p_t^{et}) = n = 2^a p_1^{e1} p_2^{e2} \cdots p_t^{et}$. Since $\phi(n) &lt; n$, this is a contradiction, and therefore, the only $n$'s that apply are the powers of 2.  Is this right? Also, we were asked to find $n$ such that $\phi(n) = n/3$. How would I go about that one?
59684
I have encountered this question in a coding competition and want the formula for $f(n)$. Is there any way to do this?
70335
I did the following proof and I was wondering if its valid. It feels wrong because I didn't actually test the case when purportedly $n$ is not prime, but please feel free to correct me.  Assume there exists $n$ such that $\phi(n) = 14$. Assume $n$ is prime. Then $\phi(n) = n-1$. Then here, n-1 = 14, so n = 15.  We know since Euler's totient function is multiplicative that $\phi(xy)$ = $\phi(x)\phi(y)$, so $\phi(15) = \phi(3)\phi(5)$, but alas $\phi(3)\phi(5) = 2\cdot4 = 8 \ne 14$. If $n$ is not prime a similar argument follows since we know then that $n$ must be composed of prime numbers by the prime factorization theorem.
45720
If $n$ is a positive integer such that the sum of all positive integers $a$ satisfying $1\leq a\leq n$ and $\gcd(a,n)=1$ is equal to $240n$ then the number of summands namely $\phi(n)$ is    120 124 240 480   My attempt:   If $n $= $p_1^{q_1}p_2^{q_2}...p_k^{q_k}$ where $p_1, p_2,...p_k$ are primes.  $240 n = \frac{n(n+1)}{2} - \frac{p_1^{q_1+1}-1}{p_1 -1}\frac{p_2^{q_2+1}-1}{p_2 -1}... \frac{p_k^{q_k+1}-1}{p_k -1}  +1 $  From here, I was not able to proceed. Guesswork tells me that the number has to be 480 because the sum is $240n$.
61551
Let $a \in \mathbb {Z}$, $n &gt; 1$ a natural number with $\gcd(a, n) = 1$, and let $r$ be the smallest positive integer such that $a^r \equiv 1 \bmod{n}$. Prove that $r \mid \phi(n)$.  Euler's generalization of Fermat's Little Theorem: If $n \in \mathbb {N}$ and $m \in \mathbb{Z}$ such that $\gcd(m, n) = 1$, then $m^{\phi(n)} \equiv 1\bmod(n)$.  By Euler's generalization I would have $a^{\phi(n)} \equiv 1\bmod{n}$.  Then I could say $a^r \equiv a^{\phi(n)} \equiv 1 \bmod{n}$. At this point I can see that $r$ clearly must be some multiple of $\phi(n)$.  If I want to show that $r \mid \phi(n)$, then I can show that $\phi(n) = rk$, for some $k \in \mathbb {Z}$.  However, I am a bit stuck about how to make this last step showing that  $\phi(n) = rk$, where $k \in \mathbb {Z}$.
68072
I was reading about Euler's totient function on wikipedia, and it eventually led me to this book on google:  .  Anyway, the books lists many assertions without proof, only references which I can't find. One I could not solve for myself said that not all even numbers are values of $\phi(n)$. The sequence of even non-values of $\phi(n)$ starts:  $14, 26, 34, 38, 50, 62,\dots$  After thinking about it for a while, I've made little headway. Looking at 14 specifically, I suppose if such a solution $a$ to $\phi(x)=14$ were to exist, $(a,m_i)=1$ for $1\leq i\leq 14$, for some $m_i\lt a$ and so there must also exist inverses $\overline{a_i}$ such that $\overline{a_i}a\equiv 1 \pmod {m_i}$ for each $i$. I'm looking for some contradiction, possibly of the Chinese Remainder Theorem, to show such $a$ cannot exist.   Is there some way to generalize which values are not taken by $\phi$, or at least explain why this is the case? I was hoping to see why $14$ is the least such integer such that this is true, but values $1$ to $13$ must be indeed taken. I suppose this would also explain why 26 is the next such value that is not taken, while $15$ to $25$ are.
111042
I want to prove basic results of cyclotomic polynomials over $\mathbb{Q}$.  $(1)\ \Phi_n(0)=1$ for all $n&gt;1$. $(2)\ \Phi_{2n}(x)=\Phi_n(-x)$ for all odd numbers $n&gt;1$.  I want use this result as definition: For every positive integer $n$, $$ x^{n}-1=\prod_{d|n} \Phi_{d}(x)$$ where $d$ runs over all positive divisors of $n$.
53923
Let $n$ and $a$ be positive integers with $a &gt; 1$. I need to show that $n$ divides $\phi(a^n -1)$.   Here, $\phi$ denotes the .  Could any one give me a hint?
13699
The problem states:  Suppose $a_0,a_1,a_2,...$ is a sequence such that $$a_0=a_1=1,\ \ \ a_{n+1}=n(a_n+a_{n-1})\ \ \ (n\ge 1).$$  Guess a formula for $a_n$, valid for $n\ge 1$, and use mathematical induction to prove that your guess is correct.  I used this equation (and check with WolframAlpha) to find the results of a few different cases.  $$a_2=2,\ a_3=6,\ a_4=24,\ a_5=120.$$  Unfortunately, I'm not really sure how I can prove this. I would appreciate any help in solving this!