Prove that \((p-3)! \equiv \dfrac{p-1}{2} mod p\)
Please, help

- Loser66

Prove that \((p-3)! \equiv \dfrac{p-1}{2} mod p\)
Please, help

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- Loser66

p is prime, p >2

- Loser66

By Wilson, we have (p-1)! =-1 (mod p)
hence (p-1)(p-2) (p-3)! = -1 (mod p)
and p-1 =1 mod p
p-2 = 2 mod p
hence 2(p-3)! =-1 mod p
then I am stuck.

- jim_thompson5910

it should be
p-1 = -1 (mod p)
p-2 = -2 (mod p)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- Loser66

yes,

- Loser66

Fortunately, the result is the same and I stuck still!! :)

- jim_thompson5910

(p-3)! = (p-1)/2 (mod p)
is equivalent to
2(p-3)! = p-1 (mod p)

- Loser66

What if I * (-1) both sides and get -2 (p-3)! = 1 mod p
that is (p-3)! is inverse of 2 mod p? then?

- jim_thompson5910

then you can use wilson's theorem to get
(p-1)! =-1 (mod p)
(p-1)(p-2) (p-3)! = -1 (mod p)
(-1)(-2)(p-3)! = -1 (mod p)
2(p-3)! = -1 (mod p)

- Loser66

@jim_thompson5910 Yes, that was what I did above.

- Loser66

but how to go further?

- jim_thompson5910

well I think that's enough to show that they are equivalent
`(p-3)! = (p-1)/2 (mod p)` is equivalent to `2(p-3)! = p-1 (mod p)`
`(p-1)! =-1 (mod p)` turns into `2(p-3)! = -1 (mod p)`
by the transitive property of equivalence, we know `(p-3)! = (p-1)/2 (mod p)` is equivalent to `(p-1)! =-1 (mod p)`
so because `p-1)! =-1 (mod p)` is true, this makes `(p-3)! = (p-1)/2 (mod p)` true too

- Loser66

aah it drove me crazy :)

- Loser66

first: we don't have (p-3)! = (p-1)/2 mod p
How ?

- jim_thompson5910

I don't understand what you're asking

- Loser66

below the line : "well I think it's enough....."
you stated : (p-3)! = (p-1)/2 mod p. My question is there, how?

- jim_thompson5910

that's what you're given

- Loser66

That is the statement we need to prove, not given information.

- jim_thompson5910

I'm saying that the thing you need to prove connects to `(p-1)! =-1 (mod p)` (in the work shown above)

- Loser66

You meant we go back ward? A = B
B leads to C
and if C true then B true then A = B hold, right?

- jim_thompson5910

what we need to prove: `(p-3)! = (p-1)/2 (mod p)`
that's equivalent to saying "we need to prove `2(p-3)! = (p-1) (mod p)` is true"
-----------------------------------------------
from above `(p-1)! =-1 (mod p)` turns into `2(p-3)! = -1 (mod p)`
since `(p-1)! =-1 (mod p)` is true, this means `2(p-3)! = -1 (mod p)` is true
so `2(p-3)! = -1 (mod p)` has been proven true
leading to `(p-3)! = (p-1)/2 (mod p)` being proven true

- Loser66

|dw:1446690142967:dw|

- jim_thompson5910

|dw:1446690425288:dw|

- Loser66

|dw:1446690433305:dw|

- Loser66

but we don't have it !! we have (p-1)! = -1

- Loser66

what we have is p-1 =1 ,

- jim_thompson5910

but you were able to show that `(p-1)! = -1 mod p` leads to `2(p-3)! = -1 (mod p)`

- jim_thompson5910

let me think of an alternative route

- Loser66

Yes, \(2(p-3)! \equiv \color{red}{-1}\) \(\implies (p-3)! \equiv \dfrac{\color {red}{-1}}{2} mod p \)
Hence if we assume that \(p-3)! \equiv \dfrac{\color {blue}{p-1}}{2}mod p\)
then we need prove \(\color{red}{-1} \equiv \color{blue}{p-1}\)
but we don't have it

- ganeshie8

you may simply divide 2 both sides

- ganeshie8

\(-1 \equiv -1+0 \equiv -1+p \equiv p-1 \pmod{p}\)

- jim_thompson5910

p-1 = -1 (mod p) is easy to prove
p = 0 (mod p)
p-1 = 0-1 (mod p)
p-1 = -1 (mod p)

- ganeshie8

adding or subtracting \(p\) wont change anything because \(p\equiv 0\) under modulo \(p\)

- Loser66

oh, yeah. I got it. Sorry for being dummy. :)

- ganeshie8

so why are we allowed to divide 2 both sides ?

- Loser66

@ganeshie8 because p is an odd prime hence p-1 is even

- ganeshie8

that's right, but thats not the correct reason

- ganeshie8

you're allowed to divide 2 both sides precicely because \(2\nmid p\),
and it follows from euclid lemma

- ganeshie8

Consider below congruence :
\(6\equiv 2\pmod{4}\)
am I allowed to divide 2 both sides here ?

- Loser66

no

- ganeshie8

both left and right sides have 2 in common, so why not ?

- Loser66

because then \(3\equiv 1 mod 4\) which is not true

- ganeshie8

that is a consequence,
doesn't answer my question..

- Loser66

oh, you want because 2 | 4,

- ganeshie8

yes, and why is that

- Loser66

tell me, please. if not, I will give you the silly answer: " because the lecture said that " lol

- ganeshie8

Okay explaining is a bit tricky, it would be easy if u see it on ur own.. .let me try..

- Loser66

To me, if reducing, we have to reduce modulo also, unless they are relative prime.

- Loser66

Like your example, if dividing by 2, it equivalences to \(3\equiv 1 mod 2\)

- ganeshie8

Exactly!

- Loser66

and it is true. but at that moment, we are working on modulo 2, not mod 4 anymore and it slightly different from what we need further.

- ganeshie8

For a prime, \(p\),
suppose \( p \mid ab\)
If \(p\nmid a\), then we can say \(p\mid b\)

- Loser66

yes

- ganeshie8

But if \(p\mid a\), then we need not have \(p\mid b\)

- ganeshie8

By exact same reasoning :
If \(p\mid 2(a-b)\), then we can say that \(p\mid (a-b)\) ONLY IF \(p\nmid 2\)

- ganeshie8

Notice that the statement \(p\mid 2(a-b)\) is same as the congruence \(2a\equiv 2b \pmod{p}\)

- ganeshie8

\[2a\equiv 2b\pmod{p}\]
we can divide \(2\) both sides because \(p\nmid 2\)

- Loser66

Got you. :)

- Loser66

Thank you so much.

- ganeshie8

np

Looking for something else?

Not the answer you are looking for? Search for more explanations.