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!
1. $\displaystyle -12\equiv{22}(\bmod.n)$
Now sum 12 on both sides: $\displaystyle 0\equiv{34}(\bmod.n)$
That means that $\displaystyle n$ must divide 34, so find the divisors of 34.
2. Remember that: $\displaystyle \phi(n)=n\cdot{\prod_{p|n}{\left(1-\frac{1}{p}\right)}}$
(where by p I mean prime)
If: $\displaystyle \phi(n)=\frac{n}{2}$ we have: $\displaystyle \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)