It's over 9,000!

Number Theory Level 3

If you know that 9001 is prime, what remainder does 8999! - 1 give when divided by 9001?

The answer is 0.

4 solutions

Curtis Clement
Jan 1, 2015

Usually Wilson's theorem states that $({p}$ -1)! $\equiv-1$ mod ${p}$ , however we can manipulate this as follows: let ${x}$ be the remainder when 8999! is divided by 9001, then 9000 ${x}$ $\equiv-x$ $\equiv-1$ mod(9001). $\therefore$ ${x}$ =1 or in other words 8999! $\equiv1$ mod (9001)

Soumava Pal
Oct 1, 2014

its wilsons theorem only!

Vishal Jindal
Dec 17, 2013

if p is a prime no. then (p-2)! %p gives remander 1 ( wilson theorem)

Bogdan Simeonov
Dec 16, 2013

Wilson's theorem states that for every prime p, p divides (p-2)! -1 (or equivalently (p-1)! + 1) .Since 9001 is prime, we can use the theorem and voila!

In fact, Wilson's theorem states that $(p-1)! \equiv -1 \pmod p$ , for any prime $p$ .

Therefore, $9000! \equiv -1 \mod 9001 \equiv 9000 \mod 9001$ .

Dividing by 9000, we have $8999! \equiv 1 \mod 9001 \Rightarrow 8999!-1 \equiv 0 \mod 9001$

minimario minimario - 7 years, 5 months ago

Does division, as you said (dividing by 9000), always work?

Niranjan Patil - 7 years, 5 months ago

Yes it always works, because (p -1,p)=1 and thus we can divide the modular equation.In this case, (9000,9001)=1 as it should be, and dividing by a number coprime to 9001 is allowed in modular equations.

Bogdan Simeonov - 7 years, 5 months ago

@Bogdan Simeonov – That shows the equivalence of p dividing (p-2)! - 1 and (p-1)! + 1

Bogdan Simeonov - 7 years, 5 months ago

It is equivalent to saying p divides (p-2)! - 1 .I wrote it down on my solution.I just used the (p-2)! one because it is more straightforward.

Bogdan Simeonov - 7 years, 5 months ago

It's over 9,000!

The answer is 0.

4 solutions

0 pending reports