IIT JEE , AIEEE Forum - Mathematics , Algebra - How to prove that 18!+1 is divisible by 23?

pardesi

ok so if u don't know number theory then here's a proof
Theorem
For every natural number x<= p-1 there exist a y,=p-1 such that xy-1 is divisible by p provided p is a prime and such y is unique
Proof
.Clearly any number not divisible by p on dividing by p will leave remainder from 1 to p-1
Let each pair of such numbers xy where y runs over all numbers 1,2,3...p-1 that is x,2x,3x...(p-1)x be divided by p then they will leave remainder from 1 to p-1 but if for one of the y's it is 1 we are done
if none give 1 as remainder then we have p-1 numbers(x,2x,3x...) and a possible p-2 remainders (2,3,...p-1)
so some two of them leave the same remainder say sx and vx then sx-vx must be divisible by p
since p is a prime it either divides x or s-v but both of them are less than p-i
a contradiction so we are done with the proof.
clearly y has to be unique because if anothe y' exists then xy and xy' leave same remainder hence xy-y') should be divisible by p but clearly that won't happen

Proof of Wilson's theorem
by the above stated theorem we get for every number
1,2,...p-1 there exist another number belonging such that their product leaves a remainder 1 when divided by p
so we can have pairs of numbers
let 1' denote the number with which one is paired 2' with which 2 is paired....
NOTE 1 pairs with itself and p-1 with itself.Rest have different numbers as pairs
also we know if ab leaves remainder 1 on dividing by p and cd also 1 then abcd leaves 1 as remainder on dividing by p
(p-1)!=1.2.3...(p-1) =(1)(2.2')(3.3').....((p-1))
but each except p-i and i is paired and p-1 leaves a remainder -1 on dividing by p
so (p-1)! +1 is divisible by p
for rest follow siddharth's proof

Ask & Discuss Questions with Community & Experts