Number Theory - Primes and Eulers equation

• Aug 9th 2007, 01:12 AM
moolimanj
Number Theory - Primes and Eulers equation
I really hate these types of questions. Can anyone help please?
• Aug 9th 2007, 05:22 AM
ThePerfectHacker
1. Given $\displaystyle n>1$ in prime factorized form $\displaystyle n=p_1^{a_1}...p_m^{a_m}$ then the number of divisors is $\displaystyle (a_1+1)...(a_m+1)$.

Use this to try to find the answer.
• Aug 9th 2007, 05:26 AM
ThePerfectHacker
2. Since $\displaystyle n$ is prime it means $\displaystyle \sigma (n) = n+1$. Thus, $\displaystyle n+2\sigma (n) = n+2(n+1)$. Show this is not divisible by three by contradiction.

If $\displaystyle n=p^2$ then $\displaystyle \sigma (p^2)=1+p+p^2$. And thus, $\displaystyle n+2\sigma (n) = 3p^2+2p+2 \equiv 2p+2 \equiv p+1\equiv 0 (\bmod 3)$.

Try to do the last one by substituting $\displaystyle \sigma (pq) = 1+p+q+pq$ into the expression and seeing what you get.
• Aug 9th 2007, 05:31 AM
ThePerfectHacker
3. We can write $\displaystyle n=p^a m$ where $\displaystyle p\not | m \mbox{ and }a\geq 2$. Thus, $\displaystyle \gcd (p_a,m)=1$.

Then,
$\displaystyle \phi (n) = \phi (p^a) \phi (m)$
$\displaystyle \phi \left( \frac{n}{p} \right) = \phi (p^{a-1})\phi(m)$

Use the above equation to reach the relationship you are trying to show.
• Aug 9th 2007, 10:55 AM
topsquark
Quote:

Originally Posted by ThePerfectHacker
2. Since $\displaystyle n$ is prime it means $\displaystyle \sigma (n) = n+1$. Thus, $\displaystyle n+2\sigma (n) = n+2(n+1)$. Show this is not divisible by three by contradiction.

If $\displaystyle n=p^2$ then $\displaystyle \sigma (p^2)=1+p+p^2$. And thus, $\displaystyle n+2\sigma (n) = 3p^2+2p+2 \equiv 2p+2 \equiv p+1\equiv 0 (\bmod 3)$.

Try to do the last one by substituting $\displaystyle \sigma (pq) = 1+p+q+pq$ into the expression and seeing what you get.

I'm curious. What is the $\displaystyle \sigma$ function?

-Dan
• Aug 9th 2007, 11:39 AM
ThePerfectHacker
Quote:

Originally Posted by topsquark
I'm curious. What is the $\displaystyle \sigma$ function?

-Dan

The SUM of all divisors.