Least positive residue of $463! \bmod 479$

96 Views Asked by At

As the title says, I am struck on a very simple problem. I have tried applying Wilson's theorem but I have no idea where to proceed from there. I know 479 is a prime number, so I don't think I can use chinese remainder theorem either.

Any help is greatly appreciated, thank you!

2

There are 2 best solutions below

2
On

$$463! \equiv 478!(464\cdot 465\cdots 478)^{-1} \equiv -1(-15\cdot -14 \cdots -1)^{-1} \pmod{479}.$$

0
On

Since $479$ is prime, every number from $1$ to $478$ has a multiplicative inverse in the same list; because of this, most numbers in $463!$ will get cancelled out to 1 by their counterparts, leaving only $469^{-1} = (-10)^{-1}$ and similar to deal with. But since we know their inverses, we can instead multiply those together (much easier) and find the inverse of that to finish the job.

Note that $1$ and $-1$ are their own inverses; in addition, since $15<\sqrt {479}$ we know that there are no other pairs of inverses entirely contained within $463!$.