# Thread: I need a help on a couple problems...

1. ## I need a help on a couple problems...

I am having trouble with 2 problems for my class. They are:

1. Find all values of n such that -12=22(mod n).

2. Prove that phi(n)=n/2 if and only if n=2^k for some positive integer k.

Thanks for the help!

2. 1. $-12\equiv{22}(\bmod.n)$

Now sum 12 on both sides: $0\equiv{34}(\bmod.n)$

That means that $n$ must divide 34, so find the divisors of 34.

2. Remember that: $\phi(n)=n\cdot{\prod_{p|n}{\left(1-\frac{1}{p}\right)}}$
(where by p I mean prime)

If: $\phi(n)=\frac{n}{2}$ we have: $\frac{1}{2}=\prod_{p|n}{\left(1-\frac{1}{p}\right)}$

And that can happen iff 2 is the only prime divisor of n. (Try working with divisibility)