Beautiful Attributes

Number Theory Level 3

$\large{\begin{cases} 399! \equiv a \pmod {401} \\ 400! \equiv b \pmod {401} \end{cases}}$

If $a,b$ are the smallest possible positive integers satisfying the above modular equalities, find the value of $\displaystyle \dfrac{a+b}{401}$ correct upto three places of decimals.

Note: You may use the fact that 401 is a prime number.

The answer is 1.000.

1 solution

Brian Charlesworth
Sep 18, 2015

Since $401$ is prime, we know from Wilson's Theorem that

$400! \equiv -1 \pmod{401} \equiv 400 \pmod{401}.$

Now this implies that $400! = 400 + 401n$ for some integer $n,$ and so

$400! - 400 = 401n \Longrightarrow 400(399! - 1) = 401n \Longrightarrow 400|n,$ since $gcd(400,401) = 1.$

Thus $400(399! - 1) = 401*400m$ for some integer $m,$ and so

$399! - 1 = 401m,$ i.e., $399! \equiv 1 \pmod{401}.$

Thus $\dfrac{a + b}{401} = \dfrac{400 + 1}{401} = \boxed{1}.$

Nice use of Wilson's Theorem and Divisibility Principles :)

@Brian Charlesworth Instead of linking Wilson's Theorem to it's wikipedia article, why don't you change it to the wiki from Brilliant? Here's the link to Wilson's Theorem Wiki from Brilliant - Wilson's Theorem

Satyajit Mohanty - 5 years, 9 months ago

Thanks. I'll remember to link to Brilliant wikis in the future. :)

Brian Charlesworth - 5 years, 8 months ago

The last part can be done a little faster: since 401 is prime the integers modulo 401 form a field, so that division is defined. Use $400 \equiv -1$ : $399! = \frac{400!}{400} \equiv \frac{-1}{-1} = 1$ .

Arjen Vreugdenhil - 5 years, 8 months ago

Beautiful Attributes

The answer is 1.000.

1 solution

0 pending reports