Can Wilson divide the product by the sum?

Number Theory Level 3

Wilson picks a number k k which is the predecessor of a prime. He computes a a as the product of all natural numbers less than or equal to k k and b b as the sum of all natural numbers less than or equal to k k .

What is a a congruent to when divided by b b ?

1 1 a − b a - b 0 0 k k

Shubhrajit Sadhukhan by Shubhrajit Sadhukhan , 16, India

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

For k = 1 k = 1 , 1 ! ≡ 1 m o d 1 1! \equiv 1 \mod 1

For k ≠ 1 k ≠ 1 :

From Wilson's theorem ,

k ! ≡ − 1 m o d k + 1 k! \equiv -1 \mod k + 1

k ! ≡ k m o d k + 1 k! \equiv k \mod k + 1

As k ∣ k ! k|k! and k k is even,

k ! ≡ 0 m o d k / 2 k! \equiv 0 \mod k/2

k ! ≡ k m o d k / 2 k! \equiv k \mod k/2

Combining the moduli,

k ! ≡ k m o d ( k + 1 ) k / 2 k! \equiv k \mod (k + 1)k/2

∴ a ≡ k m o d b \therefore a \equiv k \mod b

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...