Question

For which integers n is phi (n) = n/2
Please, help

Answer 1

phi (n) is an integer, hence n must be an even number to get n/2 = integer
hence \(n = 2^a k\) where k is odd.

Answer 2

i think that goes 2^k numbers we can prove that

Answer 3

u are on the right track lol

Answer 4

\(\phi (n) = \phi (2^a) *\phi (k) = 2^{a-1}k\), then?

Answer 5

well if there is k odd then there is some odd integer lets say i<=k, such that gcd(i,n) is not 1

Answer 6

so k need to be even thus k=2h and again we would have another integer added to n/2
so we kinda reach k can be of the form 2^g only.

Answer 7

no way!! n is even, i < = k is odd, how (i, n ) is not 1?

Answer 8

k is not even, because if we set n = 2^a k, then k must be odd. (all even goes to 2^)

Answer 9

=)
let n=6
gcd(6,3)=3 for example.

Answer 10

oh yeah, my stupidity. :)

Answer 11

nope its ok, i wanted u to see the contradiction to find out that k can be of the form 2^g or something.

Answer 12

so lets try to prove this shall we ?
phi(n)=n/2 iff n=2^k

Answer 13

show me, please

Answer 14

<--- when n=2^k then for all even numbers 2m, gcd(2m,n) is not 1. (maybe 2 or 2^i for i<k), and we have from 1 to n, n/2 even numbers.

Answer 15

is it not that we need prove
--> if n = 2^k, then phi (n) = n/2
<--, if phi (n) = n/2, then n=2^k

Answer 16

--->ph(n)=n/2 then n is even , let \( n= 2^{a_1}p_1^{a_2}p_2^{a_3}....\) so for all evens 2m
gcd(2m, n) is not 1, means phi(n)>=n/2 as we have other prime factors for n but not 2, so the only case we have is when n have only prime factors of 2.

Answer 17

oh! @Loser66 do i make sense to u or i just confused u ?

Answer 18

I don't get why \(gcd (2m,n)\neq 1, ~then~~\phi(n)\geq n/2\)

Answer 19

ok so phi(n)=n/2 means n even right ?

Answer 20

yes

Answer 21

so for even numbers 2m from m=1 to m=n/2
gcd(2m,n) is not 1 (it can be 2 or 2i) right ?

Answer 22

oh sorry that inequality should be
phi(n) <=n/2
pardon.

Answer 23

it's ok, got you

Answer 24

so now at most we have n/2 of numbers are relatively prime with n, assume n=2^ak and k is odd factor, then phi(n)<n/2.

Answer 25

ok

Answer 26

I got it, friend. Thank you so much:)

Answer 27

you are welcome <3