1. ## Congruence problem

Hi all, I'm stumped on this.

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

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

I believe I have to show that $\displaystyle \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.

2. Originally Posted by Bacterius
Hi all, I'm stumped on this.

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

$\displaystyle (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 $\displaystyle m=5\,,\,a=3$: you're saying that $\displaystyle 4!\cdot3\cdot2^3=3\!\!\!\!\pmod 5$....but $\displaystyle 4!=-1=4\!\!\!\!\pmod 5\,,\,2^3=3\!\!\!\!\pmod 5$, so:

$\displaystyle 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

3. You are not wrong, I mistakenly wrote up the wrong problem, now I edited to write the correct problem.

4. Originally Posted by Bacterius
Hi all, I'm stumped on this.

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

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

I believe I have to show that $\displaystyle \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 $\displaystyle (\frac{(2m-1)!}{m}, m) = 1$. Now, can you see why the fact that m is prime (and thus for every $\displaystyle m < k < 2m ,~ (m,k)=1$) helps here?

5. Yes, I understand better now, thanks Defunkt.

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

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

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

Dividing both sides by $\displaystyle m$ thus yields :

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

And thus :

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

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

I don't know if this is a correct proof (in the methods used, for instance).

6. Originally Posted by Bacterius
Yes, I understand better now, thanks Defunkt.

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

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

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

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

And thus :

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

Because $\displaystyle 1 < a < m$ and $\displaystyle m$ is prime, so $\displaystyle a$ cannot divide $\displaystyle 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, $\displaystyle \forall m \in \mathbb{N} ~ \frac{(2m-1)!}{m} \equiv 1 \pmod{m}$. But take, for instance, $\displaystyle m=4$, then: $\displaystyle \frac{(2m-1)!}{m} = \frac{7!}{4} = \frac{5040}{4} = 1260 \equiv 0\pmod{4}$

Why did this happen? because from the numbers $\displaystyle \{2,3,5,6,7\}$ we can produce a new multiple of 4, ie. $\displaystyle 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)?

7. Originally Posted by Bacterius
You are not wrong, I mistakenly wrote up the wrong problem, now I edited to write the correct problem.

Twice Wilson's theorem:

$\displaystyle (2m-1)!=1\cdot2\cdot,\ldots,\cdot(m-1)\cdot m\cdot(m+1)\cdot,\ldots,\cdot(2m-1)=$ $\displaystyle (-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 $\displaystyle \left(\frac{(2m-1)!}{m},m\right)=1$ , but we need, as shown above, something stronger: $\displaystyle \frac{(2m-1)!}{m}=1\!\!\!\!\pmod m$

Tonio

8. Originally Posted by tonio
Twice Wilson's theorem:

$\displaystyle (2m-1)!=1\cdot2\cdot,\ldots,\cdot(m-1)\cdot m\cdot(m+1)\cdot,\ldots,\cdot(2m-1)=$ $\displaystyle (-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 $\displaystyle \left(\frac{(2m-1)!}{m},m\right)=1$ , but we need, as shown above, something stronger: $\displaystyle \frac{(2m-1)!}{m}=1\!\!\!\!\pmod m$

Tonio
Well, if $\displaystyle \left(\frac{(2m-1)!}{m},m\right)=1 \Rightarrow$ $\displaystyle \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 $\displaystyle (2m-1)! \equiv m \pmod{m}$; if we let $\displaystyle t = (m-1)!, ~ k = (m+1)(m+2)...(2m-1)$ then $\displaystyle (2m-1)! = ktm \equiv m \pmod{m}$

9. I see. So I should have used the fact that $\displaystyle m$ is prime by saying that :

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

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

10. Originally Posted by Bacterius
I see. So I should have used the fact that $\displaystyle m$ is prime by saying that :

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

$\displaystyle \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 $\displaystyle a,b \in \{2,...,m-1,m+1,...,2m-1\}, ~ a\neq b$ such that $\displaystyle m|ab$ (hint: look at their prime factorization).

11. This is the kind of explanation that I find hard to give, but I'll give it a try :

Since $\displaystyle m$ is prime, it can only divide numbers in the form $\displaystyle k m$ with $\displaystyle k \in \mathbb{N}$. Only one such number exists in the set $\displaystyle \{2, 3, 4, ... ,2 m - 1\}$, which is $\displaystyle 1 \times m = m$, which trivially divides $\displaystyle m$. Thus, only $\displaystyle m$ divides $\displaystyle (2m - 1)!$.

12. Originally Posted by Bacterius
This is the kind of explanation that I find hard to give, but I'll give it a try :

Since $\displaystyle m$ is prime, it can only divide numbers in the form $\displaystyle k m$ with $\displaystyle k \in \mathbb{N}$. Only one such number exists in the set $\displaystyle \{2, 3, 4, ... ,2 m - 1\}$, which is $\displaystyle 1 \times m = m$, which trivially divides $\displaystyle m$. Thus, only $\displaystyle m$ divides $\displaystyle (2m - 1)!$.
Try to understand the problem we have here at first - it is trivial that the only element from $\displaystyle \{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 $\displaystyle gcd(\frac{(2m-1)!}{m},m) = 1$.

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

Let k be a prime and $\displaystyle a_1,...,a_j \in \mathbb{N} ~ \text{such that}$ $\displaystyle (a_i,m)=1 ~ \forall 1 \leq i \leq j$, then: $\displaystyle (\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.

13. Originally Posted by Defunkt
Well, if $\displaystyle \left(\frac{(2m-1)!}{m},m\right)=1 \Rightarrow$ $\displaystyle \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, $\displaystyle (2,5)=1$ , but of course this doesn't mean $\displaystyle 2=1\!\!\!\!\pmod 5$ ...The same can be said, of course, for non-primes.
The problem is precisely to prove that $\displaystyle \frac{(2m-1)!}{m}=1\!\!\!\!\pmod m$ whenever $\displaystyle 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 $\displaystyle \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 $\displaystyle (2m-1)! \equiv m \pmod{m}$; if we let $\displaystyle t = (m-1)!, ~ k = (m+1)(m+2)...(2m-1)$ then $\displaystyle (2m-1)! = ktm \equiv m \pmod{m}$
.

14. Originally Posted by tonio
Twice Wilson's theorem:

$\displaystyle (2m-1)!=1\cdot2\cdot,\ldots,\cdot(m-1)\cdot m\cdot(m+1)\cdot,\ldots,\cdot(2m-1)=$ $\displaystyle (-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 $\displaystyle \left(\frac{(2m-1)!}{m},m\right)=1$ , but we need, as shown above, something stronger: $\displaystyle \frac{(2m-1)!}{m}=1\!\!\!\!\pmod m$

Tonio
I agree that the condition that $\displaystyle (2m-1)!,m$ are coprime is not enough. Question though, why is $\displaystyle (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 $\displaystyle m=7$ we see that $\displaystyle (7+1)\cdots(2*7-1)=1235520$ and that $\displaystyle 1235520\equiv 6\text{ mod }7$.

Am I misinterpreting something"?

15. $\displaystyle -1 \equiv -1 + 7 \equiv 6 \pmod{7}$
It is just a quicker way to express $\displaystyle 7 - 1$.

Page 1 of 2 12 Last