# Thread: Congruence problem?

1. ## Congruence problem?

Suppose that the positive integer n has the property that $n + \sigma(n)$ is divisible by 3.

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

if $n = pq$ then

$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 $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 $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?

2. ## 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?

3. ## Re: Congruence problem?

If a number is congruent to 0 modulo 3, that means it is divisible by 3. But, $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.

4. ## Re: Congruence problem?

I think I see this now. Is it that as $p < q$ and $3$ is the smallest odd prime, $q$ will always have to be larger than $3$ to satisfy $p < q$? And seeing as $3$ is the only prime modulo 0 to 3 it only leaves the other two least positive residuals 1 and 2 as possibilities.

$\sigma(n)$ is the sum of divisors of $n$.

5. ## 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.