# Congruence problem?

• Jun 6th 2014, 01:38 AM
alyosha2
Congruence problem?
Suppose that the positive integer n has the property that $\displaystyle n + \sigma(n)$ is divisible by 3.

if $\displaystyle n = pq$, where $\displaystyle p$ and $\displaystyle q$ are distinct odd primes with$\displaystyle p < q$, then p = 3 and $\displaystyle q \equiv 5 (mod 6$).

if $\displaystyle n = pq$ then

$\displaystyle n + \sigma(n) = pq + (pq+ p + q + 1) = 2pq + p + q + 1$

working modulo 3, p can take any of the values 0, 1, 2 but q can take only values 1 or 2 since $\displaystyle q > 3$ is prime.

Now, I can understand why p can only take values 0, 1, 2, but why can q only take values 1 or 2? q > 3 is prime? I don't understand what is meant by this. Obviously and $\displaystyle q > 3$ is not prime for all q, and if q is defined as a odd prime this is just a pointless statement, so what does it mean and why does it put restrictions on what values q can take modulo 3?
• Jun 6th 2014, 09:40 AM
romsek
Re: Congruence problem?
reading this I'm not sure what you're trying to prove and I'm not convinced you understand what $\sigma(n)$ means.

Could you post the original problem?
• Jun 6th 2014, 10:01 AM
SlipEternal
Re: Congruence problem?
If a number is congruent to 0 modulo 3, that means it is divisible by 3. But, $\displaystyle q$ is a prime greater than 3, so it is not divisible by 3. Since it is prime, it is only divisible by 1 and itself.
• Jun 6th 2014, 05:15 PM
alyosha2
Re: Congruence problem?
I think I see this now. Is it that as $\displaystyle p < q$ and $\displaystyle 3$ is the smallest odd prime, $\displaystyle q$ will always have to be larger than $\displaystyle 3$ to satisfy$\displaystyle p < q$? And seeing as $\displaystyle 3$ is the only prime modulo 0 to 3 it only leaves the other two least positive residuals 1 and 2 as possibilities.

$\displaystyle \sigma(n)$ is the sum of divisors of $\displaystyle n$.
• Jun 7th 2014, 01:51 AM
johng
Re: Congruence problem?
Hi,
Here's your problem as I understand it:
Let n=pq be the product of odd primes p and q with p<q. Assume 3 divides the sum $s=n+\sigma(n)=pq+(p+1)(q+1)$. Then p is 3 and q is congruent to 5 mod 6.
Hints on the proof:
First suppose 3 does not divide n; i.e. neither p nor q is 3. Then both p and q are non-zero mod 3. Consider the possibilities for p mod 3 and q mod 3.
1. Both are 1 mod 3. Then s is $1+2\cdot2=2$ mod 3, a contradiction.
2. Similarly for both 2 mod 3.
3. Similarly for one is 1 mod 3 and the other is 2 mod 3.
So 3 divides n and thus p=3.
Once p=3, you should be able to quickly get that q is congruent to 5 mod 6 by first showing that q is 2 mod 3 and then use the fact that q is odd.