Question

show that if n = 2phi(n) , where n is a positive integer, then n = 2^j for some positive integer j
Please, help

Answer 1

same with previous question =)

Hint:-
n=2phi(n)
phi(n)=n/2

Answer 2

Let \(n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}\)
\(\phi(n) = n \prod (\dfrac{p_i-1}{p_i})\)
\(2\phi (n) = 2n\prod(\frac{p_i-1}{p_i})=n \implies 2\prod(\dfrac{p_i-1}{p_i}) =1\)

Answer 3

@ikram002p although they look alike but I don't think they want me to solve them the same. This is the problem next to the previous problem. If there is no different, why do they arrange them separately?

Answer 4

hence \(2(p_1-1)(p_2-1)...(p_k -1) = p_1p_2...p_k\)
Then I stuck. ;)

Answer 5

i think it's only playing with minds :O . ok i'll figure other solution for u don't worry :)

Answer 6

Hint :

\(p-1 \gt 1\) for all \(p\ne 2\)

Answer 7

then? how it forced p =2?

Answer 8

n is even as \( n=2\phi(n)\) , thus \(n = 2^{a_1}p_2^{a_2}...p_k^{a_k} \),all distinct primes. so for all numbers from 1 to n-1, we have half of them (even numbers) that are not relatively prime to n , so \(n>=2\phi(n)\), assume there exist a factor \(p_i \)of n is not 2 then there exist at least one odd number 1< j<n which is not relatively prime to n thus \(n>2\phi(n) \) which is a contradiction.

Answer 9

moreover, if \(p_i =2\) then the right hand side has the required form 2^j , but the left hand side is just 2.

Answer 10

that looks good to me

Answer 11

ikram's recent reply

Answer 12

Yes, I know, since it looks like the logic on the previous one which is phi ( n) = n/2, find n

Answer 13

I got it @ikram002p Thank you so much.

Answer 14

wait no i said i'm trying to figure out some other method -.-
i posted this as remark

Answer 15

would it be right using contrapositive like, show that if \(n \neq 2^j\) for some integer j then \(n\neq 2\phi(n)\)

Answer 16

and u can use counterexample like \(n=p^j \) for odd p hmm idk u shouldn't close the question that fast -.- .

Answer 17

ok, let try one more time

Answer 18

ur earlier method
\(2\phi (n) = 2n\prod(\frac{p_i-1}{p_i})=n \)

so we need to show that
\(2\prod(\dfrac{p_i-1}{p_i}) =1\)

Answer 19

n is even, hence \(n = 2^s p_1^{a_1}p_2^{a_2}...p_k^{a_k}\)

Answer 20

why? it is available there, just cancel n both sides, right?

Answer 21

consider primes set {2,3,5,7...}
\(\dfrac {1}{2}\times \dfrac{2}{3}\times \dfrac {4}{5}....\times \frac{p_i-1}{p_i} \) is decreasing as p_i increase right ? so its like have a upper bound of 1/2 agree ?

Answer 22

hey, I don't get what you mean by saying that the sequence is decreasing . is it not that 1/2 < 2/3< 4/5<...
how is it decreasing?

Answer 23

oh! i didn't say "sequence", i said the whole term \(\dfrac {1}{2}\times \dfrac{2}{3}\times \dfrac {4}{5}....\times \frac{p_i-1}{p_i} \) is decreasing.

Answer 24

nvm then its another stupid method, i should sleep now. goodnight.

Answer 25

Good night, friend. I do appreciate. :)

Answer 26

Oh, I gooooooot it hehehe
\(2(p_1-1)(p_2-1)...(p_k -1) = p_1p_2...p_k\)
but \(p_i -1\) is even, and \((p_i-1) | p_1p_2...p_k\)
That forced each of p_i must be even. that is none of them is odd, hence n = 2^j

Answer 27

i logged in again to write that =) glad u got it.

Answer 28

:)