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

tarinbansal

Prove that 18!+1 is divisible by 23.

Salutes assured.

siddhartha100

22!+1=0 mod 23[as per Wilsons theorem prime (p-1)!+1=0 mod p]

=>22.21.20.19.18!+1=0 mod 23[in usual notation a=b mod n means a-b is divisible by n]

=>175560.18!+1=0 mod 23.............................1

175559=0 mod 23

=>18!.175559=0 mod 23

=>18!(175560-1)=0 mod 23

=>18!.175560-18!=0 mod 23..............................2

sutracting 2 from 1

175560.18!+1-(18!.175560-18!)=0 mod 23

18!+1=0 mod 23

tarinbansal

yaar siddharth kuch steps samajh nahi aaye-
What is this ''0 mod 23''?
Where did this come from=>175559=0 mod 23
And how did the steps after this come from?

Please explain in a little more detail. I promise to give you a salute.

nadeemoidu

First of all, this method of proving divisibilty problems does not come under jee syllabus. but it is useful for olympiads

a=b( mod n) means that a and b both leave the same remainder on dividing by n.
It is to be read as a is congruent to b modulo n.
So a=0(mod n) means that a is divisible by n.

it is a useful notation as we can use many properties like
a=b( mod n) and c = d( mod n)
implies that

a+c=b+d(mod n)

ac=bd( mod n)

a^p = b^p ( mod n)
and so on.

Also there are some little more complicated theorems like as siddarth said
Wilson's theorem states that (p-1)! +1 = 0( mod p) for all prime p.

My advise is that dont concentrate on this as it is not in the JEE syllabus. JEE divisibility questions are usually linked to binomial theorem

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

tarinbansal

Thanx guys,
I think mujhe is question pe zyada dimaag nahi maarna chahiye.
anyway here are rates for all of you.

Ask & Discuss Questions with Community & Experts