Question

show that \(\large (p-1)!^{p} + 1\) is divisible by \(\large p^2\)

\(p\) is an odd prime

Answer 1

Uh, do you really need help or are you just testing us ?

Answer 2

XD

Answer 3

Welcome to OS ^^^

Answer 4

naa testing the ghost who comes here ;)

Answer 5

thank, what do I do first?

Answer 6

I come to these problems so I can feel stupid while I watch @Marki and @ganeshie8 do things I can barely understand.
I enjoy the show, though :)

Answer 7

yaaaaaaaaaay

Answer 8

XD found this cool property in the morning while trying @PFEH.1999 's recent problem

Answer 9

p is an odd prime. Right ?

Answer 10

@ReadytoLearn_Student double click below for a spoiler :)

\(\color{white}{wilson theorem }\)

Answer 11

yes p is odd prime, let me add that to the main question thanks vishy :)

Answer 12

:) yw

Answer 13

Okay lets see

1. Parity of both LHS and RHS is same (both are odd) :D

Answer 14

well idk welson said this
\((p-1)!=-1 \mod p\)
thus
\((p-1)!=-1 \mod p^2\)

since p is odd
\((p-1)!^p=-1 \mod p^2\)
and we get

\((p-1)!^p=-1 \mod p^2 \)

Answer 15

\(\large\tt \begin{align} \color{black}{\dfrac{((p-1)!)^p+1}{p^2}\hspace{.33em}\\~\\
\implies \dfrac{1}{p}\times \dfrac{((p-1)!)^p+1}{p}\hspace{.33em}\\~\\
\implies \dfrac{1}{p}\times \dfrac{((-1))^p+1}{p}------(wilson ~theorm)\hspace{.33em}\\~\\
\implies \dfrac{1}{p}\times \dfrac{(-1)+1}{p}------(as~p~is~odd)\hspace{.33em}\\~\\
\implies \dfrac{1}{p}\times \dfrac{0}{p}\hspace{.33em}\\~\\
}\end{align}\)

Answer 16

nice

Answer 17

but 1/p is not integer so ...

Answer 18

its a very good try, but it breaks in the end

p|a need not imply p^n | a

Answer 19

yes thats correct

Answer 20

suppose a|p, below logic wont work :

\[\dfrac{a}{p^n} =\dfrac{1}{p^{n-1}}\cdot \dfrac{a}{p}~ \stackrel{\color{red}{?}}{=}~\dfrac{1}{p^{n-1}}\cdot 0 \]

Answer 21

but is it true for \((mod ~p)\)

Answer 22

yes wilson gives us
\[(p-1)! \equiv -1 \pmod p\]

Answer 23

ok what about this
\(p(p-1)!=-p \mod p^2\)
\((p(p-1)!)^p=-p^p \mod p^2\)
\(p^p(p-1)!^p=-p^p \mod p^2\)
\(p^p(p-1)!^p+p^p=0 \mod p^2\)
\(p^p((p-1)!^p+1)=0 \mod p^2\)

Answer 24

lol that leads to nothing

Answer 25

yes you're not allowed to cancel p^p

Answer 26

i dint cancel i moved it to the other side

Answer 27

right, im talking about the next step

Answer 28

to conclude, you need to cancel p^p
but you're not allowed to cancel p^p because gcd(p^2, p^p) is not 1

Answer 29

p^2|p^p so thats why close road

Answer 30

Exactly ^

Answer 31

yeah thats why im trying something else without wilson :P

Answer 32

i give up , i'll just set and see

Answer 33

is this an counter example
https://www.wolframalpha.com/input/?i=is+%28%2819-1%29%21%29%5E%7B19%7D%2B1+mod+19%5E2%3D0+%3F

Answer 34

https://www.wolframalpha.com/input/?i=%28%2819-1%29%21%29%5E%2819%29%2B1+mod+19%5E2

Answer 35

O_0

Answer 36

hmm yeah it works now

Answer 37

Looks perfect!

Answer 38

:\

Answer 39

there should be another way to work this w/o using binomial thm
euler generalization mightalso work

Answer 40

we need binomial to generate the (p,p-1)pk term hmm

Answer 41

thats a good catch :) yes that looks like a typo

Answer 42

idk how u'll do it with euler
(p-1)!^(p^2-p)=1 mod p^2 hmm

Answer 43

\(\Large \text{from Wilson we got }\\ \Large
(p-1)! \equiv -1 \pmod p
\text{ so } (p-1)!=pk-1\\ \Large \text{ with binomial we got }\\ \Large
\begin{align*}
(pk-1)^p&= \sum _{i=0}^p\binom{p}{i}(pk)^{p-i}(-1)^i\\
&= p^2 \sum _{i=0}^{p-2}\binom{p}{i}(pk)^{p-i-2}(-1)^i+\binom{p}{p-1}pk-1\\
&= p^2 \sum _{i=0}^{p-2}\binom{p}{i}(pk)^{p-i-2}(-1)^i+p^2k-1\\
&= p^2 (\sum _{i=0}^{p-2}\binom{p}{i}(pk)^{p-i-2}(-1)^i+k)-1\\
\end{align*}\\\)

\(\Large \begin{align*}
(p-1)!^{p} &= p^2 (\sum _{i=0}^{p-2}\binom{p}{i}(pk)^{p-i-2}(-1)^i+k)-1 \\
&\equiv p^2 (\sum _{i=0}^{p-2}\binom{p}{i}(pk)^{p-i-2}(-1)^i+k)-1 \mod p^2 \\
&\equiv 0-1 \mod p^2
\end{align*} \)

Answer 44

i hope no typos left :(

Answer 45

hmm , idk

Answer 46

what other method could works

Answer 47

looks neat to me

Answer 48

yeah cuz its ur method lol

Answer 49

its @PFEH.1999 's method

Answer 50

ohh

Answer 51

actually euler generalization can be derived from fermat's thm using this method
wana try ?

Answer 52

prove \(\large a^{\phi(n)} \equiv 1 \pmod n\) using Fermat's little theorem and binomial theorem

Answer 53

try it when free :)

Answer 54

ohk

Answer 55

@ganeshie8 , the proof of euler thm using multiplicative group of integers modulo n is more exciting!

Answer 56

Interesting looks there are many proofs for euler thm xD
does that use the fact that phi is a multiplicative function ?

Answer 57

if ur interesting in knowing the proof

Answer 58

it depend on the facts, that u can arrange relatively prime in multiple pairs to get order of congruent and gcd(n,all numbers relatively prime with n )=1