Find Their Negative Pairs

Number Theory Level 3

1 × 2 2 × 3 3 × ⋯ × 10 0 100 \large 1\times 2^2\times 3^3\times \cdots \times 100^{100}

If the expression above is divided by 101, the remainder will be less than 50. Find this remainder.


The answer is 10.

View wiki
William Isoroku by William Isoroku , 25, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Laurent Shorts
Apr 8, 2016

Modulus 101: 1 1 × 2 2 × ⋯ × 9 9 99 × 10 0 100 ≡ 1 1 × 2 2 × ⋯ × 5 0 50 × ( − 50 ) 51 × ( − 49 ) 52 ⋯ × ( − 1 ) 100 1^1 \times 2^2 \times \cdots \times 99^{99} \times 100^{100} \equiv 1^1 \times 2^2 \times \cdots \times 50^{50} \times (-50)^{51} \times (-49)^{52} \cdots \times (-1)^{100}

≡ ( − 1 ) 25 ⋅ ( 50 ! ) 101 ≡ − 50 ! \equiv (-1)^{25}·(50!)^{101} \equiv -50! by Fermat's little theorem .

( 50 ! ) 2 ≡ 1 × 2 × ⋯ 50 × 50 × 49 × ⋯ × 1 ≡ 1 × 2 × ⋯ × 50 × ( − 51 ) × ( − 52 ) × ⋯ × ( − 100 ) (50!)^2 \equiv 1 \times 2 \times \cdots 50 \times 50 \times 49 \times \cdots \times 1 \equiv 1 \times 2 \times \cdots \times 50 \times (-51) \times (-52) \times \cdots \times (-100)

≡ 100 ! ≡ − 1 ≡ 100 \equiv 100! \equiv -1 \equiv 100 by Wilson's theorem .

The answer is R = − a R=-a where a 2 ≡ 100 ↔ R 2 ≡ 100 a^2 \equiv 100 \leftrightarrow R^2 \equiv 100 . As 101 is prime, there are only two possibilities and we can see that R ≡ 10 R\equiv 10 or R ≡ − 10 ≡ 91 > 50 R\equiv-10\equiv 91>50 . The answer must be 10 \boxed{10} .

19 Helpful 0 Interesting 0 Brilliant 0 Confused

Is there any reason for taking R=-a since taking R=a , would be much simpler ?

Sivaramakrishnan Sivakumar - 5 years, 1 month ago

Log in to reply

As R = − 50 ! R=-50! and ( 50 ! ) 2 ≡ 100 (50!)^2\equiv 100 , if a = 50 ! a=50! , then R = − a R=-a .

Of course, a 2 ≡ 100 ⇔ ( − a ) 2 ≡ 100 a^2\equiv 100 \Leftrightarrow (-a)^2\equiv 100 , so we also have R 2 ≡ 100 R^2\equiv 100 . If we see this at once, we can just skip a a alltogether and do with this much simpler way:

R ≡ − 50 ! ⇒ R 2 ≡ ( − 50 ! ) 2 ≡ ( 50 ! ) 2 ≡ 100 R\equiv -50! \Rightarrow R^2\equiv (-50!)^2 \equiv (50!)^2 \equiv 100

Laurent Shorts - 5 years, 1 month ago

ok ok ... a is 50! .now i understand . @Laurent Shorts you can clearly state the variables so that we could understand faster . The solution is awesome ! :) thank you

Sivaramakrishnan Sivakumar - 5 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...