Page 1 of 2 12 LastLast
Results 1 to 15 of 20

Math Help - Congruence problem

  1. #1
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Congruence problem

    Hi all, I'm stumped on this.

    Prove that for m prime and a integer such as 1 < a < m, we have :

    \frac{(2m - 1)!}{m} \times a \equiv a \pmod{m}

    I believe I have to show that \frac{(2m - 1)!}{m} \equiv 1 \pmod{m}, but I just don't know how to start this.

    I've never stumbled across such a twisted problem yet ... thanks all

    EDIT : I put the wrong exercise with the wrong question ... corrected.
    Last edited by Bacterius; December 22nd 2009 at 02:24 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Bacterius View Post
    Hi all, I'm stumped on this.

    Prove that for m prime and a integer such as 1 < a < m, we have :

    (m - 1)! \times a \times 2^{m - 2} \equiv a \pmod m

    I just don't know how to prove this, I've never stumbled across such a twisted problem yet ... thanks all

    Take m=5\,,\,a=3: you're saying that 4!\cdot3\cdot2^3=3\!\!\!\!\pmod 5....but 4!=-1=4\!\!\!\!\pmod 5\,,\,2^3=3\!\!\!\!\pmod 5, so:

    4!\cdot3\cdot2^3=4\cdot3\cdot 3=1\!\!\!\!\pmod 5\neq 3\!\!\!\!\pmod 5 , and thus the claim is false....or I am wrong, of course.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    You are not wrong, I mistakenly wrote up the wrong problem, now I edited to write the correct problem.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Bacterius View Post
    Hi all, I'm stumped on this.

    Prove that for m prime and a integer such as 1 < a < m, we have :

    \frac{(2m - 1)!}{m} \times a \equiv a \pmod{m}

    I believe I have to show that \frac{(2m - 1)!}{m} \equiv 1 \pmod{m}, but I just don't know how to start this.

    I've never stumbled across such a twisted problem yet ... thanks all

    EDIT : I put the wrong exercise with the wrong question ... corrected.
    This would be equivalent to showing that (\frac{(2m-1)!}{m}, m) = 1. Now, can you see why the fact that m is prime (and thus for every m < k < 2m ,~ (m,k)=1) helps here?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Yes, I understand better now, thanks Defunkt.

    I had an idea to show it though, could this be correct :

    We know that (2m - 1)! \equiv 0 \pmod{m}

    This can be written : (2m - 1)! \equiv m \pmod{m}

    Dividing both sides by m thus yields :

    \frac{(2m - 1)!}{m} \equiv 1 \pmod{m}

    And thus :

    \frac{(2m - 1)!}{m} \times a \equiv a \pmod{m}

    Because 1 < a < m and m is prime, so a cannot divide m.

    I don't know if this is a correct proof (in the methods used, for instance).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Bacterius View Post
    Yes, I understand better now, thanks Defunkt.

    I had an idea to show it though, could this be correct :

    We know that (2m - 1)! \equiv 0 \pmod{m}

    This can be written : (2m - 1)! \equiv m \pmod{m}

    Dividing both sides by m thus yields :
    Your mistake is in this step.
    \frac{(2m - 1)!}{m} \equiv 1 \pmod{m}

    And thus :

    \frac{(2m - 1)!}{m} \times a \equiv a \pmod{m}

    Because 1 < a < m and m is prime, so a cannot divide m.

    I don't know if this is a correct proof (in the methods used, for instance).
    Note that you did not use the fact that m is prime anywhere - meaning that if this proof were true, then, specifically, \forall m \in \mathbb{N} ~ \frac{(2m-1)!}{m} \equiv 1 \pmod{m}. But take, for instance, m=4, then: \frac{(2m-1)!}{m} = \frac{7!}{4} = \frac{5040}{4} = 1260  \equiv 0\pmod{4}

    Why did this happen? because from the numbers \{2,3,5,6,7\} we can produce a new multiple of 4, ie. 2*6=12 \equiv 0 \pmod{4}. Can you see how m being prime solves this problem, and then how to incorporate this into your proof (which is perfectly fine otherwise)?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Bacterius View Post
    You are not wrong, I mistakenly wrote up the wrong problem, now I edited to write the correct problem.

    Twice Wilson's theorem:

    (2m-1)!=1\cdot2\cdot,\ldots,\cdot(m-1)\cdot m\cdot(m+1)\cdot,\ldots,\cdot(2m-1)= (-1)\cdot m\cdot (-1)\!\!\!\!\pmod m=m\!\!\!\!\pmod m , and from here follows the solution to your problem.

    It is not sufficient, imo, to prove \left(\frac{(2m-1)!}{m},m\right)=1 , but we need, as shown above, something stronger: \frac{(2m-1)!}{m}=1\!\!\!\!\pmod m

    Tonio
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by tonio View Post
    Twice Wilson's theorem:

    (2m-1)!=1\cdot2\cdot,\ldots,\cdot(m-1)\cdot m\cdot(m+1)\cdot,\ldots,\cdot(2m-1)= (-1)\cdot m\cdot (-1)\!\!\!\!\pmod m=m\!\!\!\!\pmod m , and from here follows the solution to your problem.

    It is not sufficient, imo, to prove \left(\frac{(2m-1)!}{m},m\right)=1 , but we need, as shown above, something stronger: \frac{(2m-1)!}{m}=1\!\!\!\!\pmod m

    Tonio
    Well, if \left(\frac{(2m-1)!}{m},m\right)=1 \Rightarrow  \exists x,y \in \mathbb{Z} ~ s.t. ~ x\frac{(2m-1)!}{m} + ym = 1 \overbrace{\Rightarrow}^{t = -y} x\frac{(2m-1)!}{m} = tm + 1 \equiv 1 \pmod{m}

    So these results are actually equivalent, however I don't agree that what you showed proves the claim... It is fairly trivial, even without using Wilson's theorem, that (2m-1)! \equiv m \pmod{m}; if we let t = (m-1)!, ~ k = (m+1)(m+2)...(2m-1) then (2m-1)! = ktm \equiv m \pmod{m}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    I see. So I should have used the fact that m is prime by saying that :

    Since m is prime, we know that only m divides (2m - 1)!, therefore we can say that :

    \frac{(2m - 1)!}{m} \equiv 1 \pmod{m}

    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Bacterius View Post
    I see. So I should have used the fact that m is prime by saying that :

    Since m is prime, we know that only m divides (2m - 1)!, therefore we can say that :

    \frac{(2m - 1)!}{m} \equiv 1 \pmod{m}

    Yes, this seems correct to me, however you should probably provide a more detailed explanation of why m being prime gives us that we can't have two distinct integers a,b \in \{2,...,m-1,m+1,...,2m-1\}, ~ a\neq b such that m|ab (hint: look at their prime factorization).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    This is the kind of explanation that I find hard to give, but I'll give it a try :

    Since m is prime, it can only divide numbers in the form k m with k \in \mathbb{N}. Only one such number exists in the set \{2, 3, 4, ... ,2 m - 1\}, which is 1 \times m = m, which trivially divides m. Thus, only m divides (2m - 1)!.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Bacterius View Post
    This is the kind of explanation that I find hard to give, but I'll give it a try :

    Since m is prime, it can only divide numbers in the form k m with k \in \mathbb{N}. Only one such number exists in the set \{2, 3, 4, ... ,2 m - 1\}, which is 1 \times m = m, which trivially divides m. Thus, only m divides (2m - 1)!.
    Try to understand the problem we have here at first - it is trivial that the only element from \{1,2,...,2m-1\} that m divides is m itself, however we want to show that there arent any two (or more) elements in that set that, when multiplied together, would be a multiple of m (as was the case with m=4).

    As I said in the beginning, this is actually equivalent to showing that gcd(\frac{(2m-1)!}{m},m) = 1.

    To prove the claim, first note that \frac{(2m-1)!}{m} = 1*2*...*(m-1)*(m+1)*...*(2m-1). Now, prove the following lemma:

    Let k be a prime and a_1,...,a_j \in \mathbb{N} ~ \text{such that} (a_i,m)=1 ~ \forall 1 \leq i \leq j, then: (\prod_{i=1}^{j}a_i, m) = 1. You can show this by induction or in a straight-forward way (try to make it as rigorous as you can). After you prove this, your proof will be finished once you apply the lemma to the current situation.
    Last edited by Defunkt; December 22nd 2009 at 03:58 PM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Defunkt View Post
    Well, if \left(\frac{(2m-1)!}{m},m\right)=1 \Rightarrow  \exists x,y \in \mathbb{Z} ~ s.t. ~ x\frac{(2m-1)!}{m} + ym = 1 \overbrace{\Rightarrow}^{t = -y} x\frac{(2m-1)!}{m} = tm + 1 \equiv 1 \pmod{m}

    So these results are actually equivalent,


    Not at all! For example, (2,5)=1 , but of course this doesn't mean 2=1\!\!\!\!\pmod 5 ...The same can be said, of course, for non-primes.
    The problem is precisely to prove that \frac{(2m-1)!}{m}=1\!\!\!\!\pmod m whenever m is a prime. Of course this fraction is an integer: that's trivial, as you note. What isn't trivial is that it equals precisely 1 in the (multiplicative) group \left(\mathbb{Z}\slash m\mathbb{Z}\right)^{*}, and this is what I attempted, and suceeded (unless proven wrong), to prove in my prior post.

    Tonio



    however I don't agree that what you showed proves the claim... It is fairly trivial, even without using Wilson's theorem, that (2m-1)! \equiv m \pmod{m}; if we let t = (m-1)!, ~ k = (m+1)(m+2)...(2m-1) then (2m-1)! = ktm \equiv m \pmod{m}
    .
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by tonio View Post
    Twice Wilson's theorem:

    (2m-1)!=1\cdot2\cdot,\ldots,\cdot(m-1)\cdot m\cdot(m+1)\cdot,\ldots,\cdot(2m-1)= (-1)\cdot m\cdot (-1)\!\!\!\!\pmod m=m\!\!\!\!\pmod m , and from here follows the solution to your problem.

    It is not sufficient, imo, to prove \left(\frac{(2m-1)!}{m},m\right)=1 , but we need, as shown above, something stronger: \frac{(2m-1)!}{m}=1\!\!\!\!\pmod m

    Tonio
    I agree that the condition that (2m-1)!,m are coprime is not enough. Question though, why is (m+1)\cdots (2m-1)\equiv -1\text{ mod }m by Wilson's theorem? I don't see how you are manipulating that into the required form? Anyways, taking m=7 we see that (7+1)\cdots(2*7-1)=1235520 and that 1235520\equiv 6\text{ mod }7.

    Am I misinterpreting something"?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    -1 \equiv -1 + 7 \equiv 6 \pmod{7}
    It is just a quicker way to express 7 - 1.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 29th 2011, 07:41 AM
  2. congruence problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 2nd 2009, 10:24 AM
  3. Another congruence problem
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 3rd 2009, 05:14 PM
  4. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 9th 2009, 02:14 AM
  5. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 14th 2007, 10:25 AM

Search Tags


/mathhelpforum @mathhelpforum