I need to show that if $n=2\phi(n)$, then $n=2^j$, where $n,j\in\mathbb{N}$.  I have a strong feeling that this can only be shown by contradiction. Therefore, I assumed that both $n=2\phi(n)$ and $n\neq2^j$. Then if we let, say, $n=5$, it follows that $5=2\cdot\phi(5)=8$, which is a contradiction. Hence, it must be the case that $n=2^j$.  Is this a valid proof?
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?
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?
81416
I know that there is a similar post, but I 'm trying a different proof. I will write $P$  for the set of all positive prime numbers. Question: If $\phi$ is Euler's Phi Function, we want to find all $n \in \mathbb{Z^+}$ such that $\phi(n)=4$. Answer: Let $n=p_1^{n_1}\dotsb p_k^{n_k}\in \mathbb{Z}^+$ be the factorisation of $n$ in to primes. Then $$\phi(n)=p_1^{n_1-1} \dotsb p_k^{n_k-1}(p_1-1) \dotsb (p_k-1)=4.$$ So, for any $i \in \{1,2,\cdots,k\}$ we have $p_i-1|4$. Hence, $$p_i-1\in\{1,2,4\} \iff p_i\in \{2,3,5\} \subset P.$$ Now, we can see the primes that $n$ contains: $n=2^{n_1}3^{n_2}5^{n_3}$, where  $n_1,n_2,n_3 \in \mathbb{Z}^+$. So, \begin{align*} \phi(2^{n_1}3^{n_2}5^{n_3})=4 \iff \phi(2^{n_1})\phi(3^{n_2})\phi(5^{n_3})=4  \tag{*} \end{align*} The possible cases for $n_i$ are:  $n_1=1,2,3\implies \phi(2)=1,\phi(2^2)=2, \phi(2^3)=4$ respectively $n_2=1 \implies \phi(3)=2$ $n_3=1 \implies \phi(5)=4$  All the posible combinations for the relation (*) are $\phi(5)$, $\phi(5)\phi(2)$, $\phi(3)\phi(2^2)$, $\phi(2^3)$. So, $$n \in \{5,10,12,8\}.$$ Is this completely right? Thank you.
4426
Not sure if I'm doing this correctly but this is what I've done:  Assume that $n$ is composite and suppose $2^n-1$ is a prime for $n \gt 2$. Then, $2^n-1 = 2k$ for some $k \in \Bbb Z $, $\forall n$.  But this would be a contradiction since $n \gt 2$.  I'm not sure if this a correct proof.  EDIT: I realized that it's to prove $2^n - 1$ NOT $2^{n-1}$ so my attempt above is completely wrong.
4812
Problem: $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$  My work: Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$, then we have that  $$ a^{\phi(p_i^{a_i})}\equiv 1\pmod{p_i^{a_i}} $$ by Euler's theorem. Since $\phi(p_i^{a_i}) \mid \phi(m)$, we have that $p_i^{a_i}\mid (a^{\phi(m)}-1)$ if $(a,p_i)=1$.   Beyond this, I am stuck at the moment.
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.
75621
Where $\phi(n)$ is the Euler phi function, how do you find all $n$ such that $\phi(n)|n$?
21280
I just want to know if my proof to this question is correct. First, I proved it was true for $n = 4$. $$4!&gt;2^4$$ $$24&gt;16$$ Then, I assumed that it was true for $n=k$. $$k!&gt;2^k$$ Afterwards, I tried to prove it for $n=k+1$. $$(k+1)!&gt;2^{k+1}$$ $$(k+1)k!&gt;(2)(2^k)$$ Since $k!&gt;2^k$, am I allowed to simply do $$(k+1)(2^k)&gt;(2)(2^k)$$ $$(k+1)&gt;2$$ and this is true for all $k\geq3$. Would the last two steps be illegal because I only assumed that $k!&gt;2^k$ is true?
2770
Show that if $n&gt;2$, then $(n!)^2&gt;n^n$.     My work: I tried to apply induction. So, at the induction step, I need to prove, $n^n&gt;(n+1)^{n-1}$ Here, I tried to use induction again without any luck. I also took log of both sides, but I did not get anything. Please help!
96129
I know how to prove that, if $2^n-1$ is prime and $n&gt;1$, then $n$ is prime.  But how do we prove that, if $a^n-1$ is prime and $n&gt;1$, then $a$ must equal 2?
2019
I have been boggled by this question for a while as well. Prove that $$(2a+b)(2b+a)=2^c$$  Is impossible.  I know that if a and b do exist then they must be even. I am trying to use this fact to contradict the statement. I haven also tried rewriting a and b as products of powers of twos and a odd factor
44142
I'm not sure if this proof is valid or not and could use some feedback.  Let P be the supposition that $2^n \le 2^{n+1}-2^{n-1} - 1$ for all positive integers n.   Base Case: Let n=1  $2^1 \le 2^2-2^0-1$  $2\le2$   Suppose that P holds true for some positive integer n=k  $$2^{k+1}=2*2^k$$  By inductive hypothesis:  $$2*2^k \le 2(2^{k+1}-2^{k-1}-1)$$  $$2^{k+1} \le 2^{k+2}-2^{k}-2$$   Since we know $2^{k+1} \le 2^{k+2}-2^{k}-2$, we also know $2^{k+1} \le 2^{k+2}-2^{k}-1$ because the former is always smaller.  This proves that: $$2^k \le 2^{k+1}-2^{k-1} - 1\Rightarrow 2^{k+1} \le2^{k+2}-2^{k}-1 $$
69970
The main question is :  Prove that $n^n&gt;1\times3\times5\times7\times\dots\times(2n-1)$  My approach :  We can write the R.H.S as,  $$\frac{(2n-1)!}{2\times4\times6\times\dots\times2(n-1)}$$ We can write $(2n-1)!$ as $(2n-3)!(2n-1)2(n-1)$  Thus, in this manner we can cancel out even terms till $n$ appears. I'm having trouble doing this. What I intend to do is say that any positive number's factorial is less than the number raised to itself. I welcome any alternate method. Please help.  P.S. I am still in high school and do not understand binomial theorem and induction.
16415
I'm trying to prove the following statement: $P(n) = 3^{2n-1} + 2^{n+1}$ is always a multiple of $7$  $\forall n\geq1$. I want to use induction, so the base case is $P(1) = 7$ so that's okay.  Now I need to prove that if $P(n)$ is true then $P(n+1)$ is true. So there exists a $d \in \mathbb{N}$ such that  $$ 3^{2n-1} + 2^{n+1} = 7d $$ From this I need to say that there exists a $k \in \mathbb{N}$ such that: $$ 3^{2n+1} + 2^{n+2} = 7k $$ With a little algebraic manipulation, I have managed to say: $$ 2 \cdot 3^{2n+1} + 9 \cdot 2^{n+2} = 7\cdot(18d) $$ But now I am stuck. How should I keep going?
102873
I was given this problem to Prove if $Q(n)=Q(2n)$ implies $9∣n$. Where $Q(n)$ be the sum of digits of $n$. I tried to use the fact that sum of digits is congruent to the number modulo $9$ but I had no luck. Any help is appreciated.
70085
Problem: $2^n &gt; n^2, \forall n \in \mathbb{N} , n \geq 5$ Base: $2^5 &gt; 5^2$ Induction Hypothesis: Assume for $n = k \geq 5$ that $2^k&gt;k^2$ Inductive Step: $$2^k &gt; k^2$$ $$2^k \times  2 &gt; k^2 \times 2$$ $$2^{k+1} &gt; 2k^2$$ From there I can finish the proof by asserting that $k^2 &gt; 2k+1, \forall k \in \mathbb{N} , k \geq 3$. Do I need to prove that $k^2 &gt; 2k+1, \forall k \in \mathbb{N} , k \geq 3$. Or can I substitute it into my inequality?
55620
So I need to prove the inequality :  $$n &lt; 2^n$$  by Induction.  What I have done so far is :     Step $1$: Prove that the statement is true for $n=1$   $$1&lt;2^1$$ (true)      Step $2$:    Prove that, if $p(n)$ is true, then $p(n+1)$ is also true.      Assume that $p(n): n &lt; 2^n$ is true. then :      (Add $1$ on both side to get $n+1$) : $$n+1 &lt; 2^n +1$$      (Multiply the original inequality by $2$ to get $2^{n+1}$ ) :   $$2^{n+1} &lt; 2^n . 2$$   I don't know where to go from here. In fact, I am not sure whether what I did is true or not. I appreciate any insight and help.