Results 1 to 5 of 5

Math Help - Congruence problem?

  1. #1
    Member
    Joined
    May 2009
    Posts
    109

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,485
    Thanks
    961

    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2009
    Posts
    109

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    639
    Thanks
    257

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence problem
    Posted in the Number Theory Forum
    Replies: 19
    Last Post: December 25th 2009, 07:23 PM
  2. Congruence problem with gcd
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 9th 2009, 12:18 AM
  3. Congruence problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 24th 2008, 10:54 AM
  4. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 14th 2007, 10:25 AM
  5. Congruence problem with LCM
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 19th 2007, 12:55 PM

Search Tags


/mathhelpforum @mathhelpforum