Loser66
  • Loser66
Prove that \((p-3)! \equiv \dfrac{p-1}{2} mod p\) Please, help
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
Loser66
  • Loser66
p is prime, p >2
Loser66
  • 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
  • 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
  • Loser66
yes,
Loser66
  • Loser66
Fortunately, the result is the same and I stuck still!! :)
jim_thompson5910
  • jim_thompson5910
(p-3)! = (p-1)/2 (mod p) is equivalent to 2(p-3)! = p-1 (mod p)
Loser66
  • 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
  • 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
  • Loser66
@jim_thompson5910 Yes, that was what I did above.
Loser66
  • Loser66
but how to go further?
jim_thompson5910
  • 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
  • Loser66
aah it drove me crazy :)
Loser66
  • Loser66
first: we don't have (p-3)! = (p-1)/2 mod p How ?
jim_thompson5910
  • jim_thompson5910
I don't understand what you're asking
Loser66
  • 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
  • jim_thompson5910
that's what you're given
Loser66
  • Loser66
That is the statement we need to prove, not given information.
jim_thompson5910
  • 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
  • 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
  • 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
  • Loser66
|dw:1446690142967:dw|
jim_thompson5910
  • jim_thompson5910
|dw:1446690425288:dw|
Loser66
  • Loser66
|dw:1446690433305:dw|
Loser66
  • Loser66
but we don't have it !! we have (p-1)! = -1
Loser66
  • Loser66
what we have is p-1 =1 ,
jim_thompson5910
  • jim_thompson5910
but you were able to show that `(p-1)! = -1 mod p` leads to `2(p-3)! = -1 (mod p)`
jim_thompson5910
  • jim_thompson5910
let me think of an alternative route
Loser66
  • 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
  • ganeshie8
you may simply divide 2 both sides
ganeshie8
  • ganeshie8
\(-1 \equiv -1+0 \equiv -1+p \equiv p-1 \pmod{p}\)
jim_thompson5910
  • 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
  • ganeshie8
adding or subtracting \(p\) wont change anything because \(p\equiv 0\) under modulo \(p\)
Loser66
  • Loser66
oh, yeah. I got it. Sorry for being dummy. :)
ganeshie8
  • ganeshie8
so why are we allowed to divide 2 both sides ?
Loser66
  • Loser66
@ganeshie8 because p is an odd prime hence p-1 is even
ganeshie8
  • ganeshie8
that's right, but thats not the correct reason
ganeshie8
  • ganeshie8
you're allowed to divide 2 both sides precicely because \(2\nmid p\), and it follows from euclid lemma
ganeshie8
  • ganeshie8
Consider below congruence : \(6\equiv 2\pmod{4}\) am I allowed to divide 2 both sides here ?
Loser66
  • Loser66
no
ganeshie8
  • ganeshie8
both left and right sides have 2 in common, so why not ?
Loser66
  • Loser66
because then \(3\equiv 1 mod 4\) which is not true
ganeshie8
  • ganeshie8
that is a consequence, doesn't answer my question..
Loser66
  • Loser66
oh, you want because 2 | 4,
ganeshie8
  • ganeshie8
yes, and why is that
Loser66
  • Loser66
tell me, please. if not, I will give you the silly answer: " because the lecture said that " lol
ganeshie8
  • ganeshie8
Okay explaining is a bit tricky, it would be easy if u see it on ur own.. .let me try..
Loser66
  • Loser66
To me, if reducing, we have to reduce modulo also, unless they are relative prime.
Loser66
  • Loser66
Like your example, if dividing by 2, it equivalences to \(3\equiv 1 mod 2\)
ganeshie8
  • ganeshie8
Exactly!
Loser66
  • 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
  • ganeshie8
For a prime, \(p\), suppose \( p \mid ab\) If \(p\nmid a\), then we can say \(p\mid b\)
Loser66
  • Loser66
yes
ganeshie8
  • ganeshie8
But if \(p\mid a\), then we need not have \(p\mid b\)
ganeshie8
  • 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
  • ganeshie8
Notice that the statement \(p\mid 2(a-b)\) is same as the congruence \(2a\equiv 2b \pmod{p}\)
ganeshie8
  • ganeshie8
\[2a\equiv 2b\pmod{p}\] we can divide \(2\) both sides because \(p\nmid 2\)
Loser66
  • Loser66
Got you. :)
Loser66
  • Loser66
Thank you so much.
ganeshie8
  • ganeshie8
np

Looking for something else?

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