Modulus 1009 # 2

Number Theory Level 5

$\frac{(1009^2-2)!}{1009^{1008}}$

Find the remainder when the number above is divided by 1009.

The answer is 1008.

2 solutions

Christopher Boo
Mar 25, 2015

$\begin{aligned} \displaystyle \frac{(1009^2-2)!}{1009^{1008}} &= \frac{(1009^2)!}{1009^{1008}\times1009^2\times(1009^2-1)} \\ &= \frac{(1009^2)!}{1009^{1010}\times(1009^2-1)} \\ &= \frac{(1009^2)!}{1009^{1010}} \times \frac{1}{1009^2-1}\end{aligned}$

Wilson's Theorem :

A natural number $p$ is a prime if and only if $(p-1)!\equiv -1 \mod p \\$ .

$\begin{aligned} \displaystyle \frac{(1009^2)!}{1009^{1010}} &\equiv [(1008)!]^{1010} &\mod 1009\\ &\equiv (-1)^{1010} &\mod 1009 \\ &\equiv 1&\mod 1009\end{aligned}$

$\displaystyle \frac{1}{1009^2-1} \mod 1009$

We need to find the Multiplicative Inverse of $1009^2-1$ .

Let the multiplicative inverse be $x$ , such that

$\begin{aligned} (1009^2-1)x &\equiv 1 &\mod 1009 \\ 1009^2x-x &\equiv 1 &\mod 1009 \\ x &\equiv -1 &\mod 1009\end{aligned}$

$\begin{aligned} \displaystyle \frac{(1009^2)!}{1009^{1010}} \times \frac{1}{1009^2-1} &\equiv \big(1\big) \times\big( -1\big) &\mod 1009\\ &\equiv 1008 &\mod 1009\end{aligned}$

You don't really need to use modular multiplicative inverses here. It suffices to use Wilson's Theorem along with the fact that $1009$ is a prime (and also noting that the numerator of the fraction has only $1008$ multiples of $1009$ ).

$(1009^2-2)!=\left(\prod_{k=0}^{1007}\prod_{m=1009k+1}^{1009(k+1)-1}m\right)\cdot\left(\prod_{k=1009\times 1008+1}^{1009^2-2}k\right)\cdot\left(\prod_{k=1}^{1008}1009k\right)\\ \implies \frac{(1009^2-2)!}{1009^{1008}}=\left(\prod_{k=0}^{1007}\prod_{m=1009k+1}^{1009(k+1)-1}m\right)\cdot\left(\prod_{k=1009\times 1008+1}^{1009^2-2}k\right)\cdot\left(\prod_{k=1}^{1008}k\right)$

Applying modulo $1009$ and a bit of simplifying gives,

$\frac{(1009^2-2)!}{1009^{1008}}\equiv 1008!^{1009}\cdot 1007!\equiv (-1)^{1009}\cdot 1\equiv -1\equiv 1008\pmod{1009}$

The last few steps follow from Wilson's Theorem and an extension of it which states that for any prime $p$ , we have $(p-1)!\equiv -1\pmod{p}$ and $(p-2)!\equiv 1\pmod{p}$ .

In fact, the problem can be generalized a bit. We have, for primes $p$ ,

$\frac{(p^2-2)!}{p^{p-1}}\equiv (-1)^p\equiv\begin{cases}\begin{aligned}1&&\textrm{when}~p=2\\ -1&&\textrm{otherwise}\end{aligned}\end{cases}\pmod{p}$

Prasun Biswas - 5 years, 8 months ago

+1 for generalising

Agnishom Chattopadhyay - 5 years, 4 months ago

well, the modular multiplicative inverses were easier to understand than... that :P

Alex Li - 4 years, 6 months ago

I am confused with how you simplified the second part so that you could use Wilson's theorem. Could you clarify what you did there? Thanks!

Anand Iyer - 6 years, 2 months ago

In $1009^2!$ , you have 1010 $1009$ s ( $1009(1), 1009(2),\dots , 1009(1009)$ ) ,so it can be divide by $1009^{1010}$ . Now, what we left is

$[1009(0)+1]\times[1009(0)+2]\times\dots\times[1009(0)+1008]\times 1\times$

$[1009(1)+1]\times[1009(1)+2]\times\dots\times[1009(1)+1008]\times 2\times$

$[1009(2)+1]\times[1009(2)+2]\times\dots\times[1009(2)+1008]\times 3\times$

$\vdots$

$[1009(1008)+1]\times[1009(1008)+2]\times\dots\times[1009(1008)+1008] \times 1008$

The rightmost number is the result of being divided by $1009$ . Then, take every number $n$ as $n \mod 1009$ . Finally, you will get something like

$1\times2\times \dots \times 1008 \times1$

$1\times2\times \dots \times 1008 \times2$

$1\times2\times \dots \times 1008 \times3$

$\vdots$

$1\times2\times \dots \times 1008 \times1008$

There are one $1008!$ in each row and one $1008!$ from the rightmost vertical column. Hence, there are a total of 1010 $1008!$ , Hence $[1008!]^2$ .

Christopher Boo - 6 years, 2 months ago

I think what you mean is like this

$[1009(0)+1]\times[1009(0)+2]\times\dots\times[1009(0)+1008]\times 1\times$ $[1009(1)+1]\times[1009(1)+2]\times\dots\times[1009(1)+1008]\times 2\times$ $[1009(2)+1]\times[1009(2)+2]\times\dots\times[1009(2)+1008]\times 3\times$

$\vdots$

$[1009(1007)+1]\times[1009(1007)+2]\times\dots\times[1009(1007)+1008]\times 1008\times$ $[1009(1008)+1]\times[1009(1008)+2]\times\dots\times[1009(1008)+1008]$

so we can simplify it...

$1\times2\times \dots \times 1008 \times1$

$1\times2\times \dots \times 1008 \times2$

$1\times2\times \dots \times 1008 \times3$

$\vdots$

$1\times2\times \dots \times 1008 \times1008$

$1\times2\times \dots \times 1008$

if you check your calculation from your response above you will get (1008!)^1009, this one will give result (1008!)^1010

Jeremy Karis - 5 years, 9 months ago

Arjen Vreugdenhil
Oct 19, 2015

Since 1009 is a prime number, there are 1008 factors 1009 in $(1009^2-2)!$ (namely, once for each multiple of 1009). Thus the answer is not zero.

Modulo 1009, we write $\frac{(1009^2-1)!}{1009^{1008}} \equiv 1008!\cdot 1\cdot 1008!\cdot 2 \cdot 1008!\cdot 3\cdots1008!\cdot 1008\cdot 1008! \\ \equiv (1008!)^{1010}.$ The factors in $1008!$ may be paired together in pairs of multiplicative inverses, except 1 and 1008, which are multiplicative inverses of themselves. Thus $(1008!)^{1010} \equiv (1\cdot 1008)^{1010} \equiv (-1)^{1010} \equiv 1.$

Divide out a factor $1009^2-1$ : $\frac{(1009^2-1)!}{1009^{1008}} \equiv \frac{1}{1008} \equiv \frac{1}{-1} \equiv -1 \equiv 1008$ modulo 1009. Thus the answer is $\boxed{1008}$ .

Modulus 1009 # 2

The answer is 1008.

2 solutions

0 pending reports