How many residues?

Let x x be a positive integer, p p be an odd prime and r r be a positive integer where 0 r p 1 0 \le r \le p-1 . As x x ranges over all positive multiples of p p , how many values of r r are there which satisfy ( x p 1 p ) x p 1 x r ( m o d p ) \dbinom{xp-1}{p} - \lfloor \dfrac{xp-1}{x} \rfloor \equiv r \pmod{p} ?


The answer is 1.

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

Josh Rowley
Feb 25, 2014

We will consider each of the 2 terms on the LHS separately. Firstly, ( x p 1 p ) = ( x p 1 ) ( x p 2 ) . . . ( p ( x 1 ) ) p ! \dbinom{xp-1}{p} = \dfrac{(xp-1)(xp-2)...(p(x-1))}{p!} . Evidently p ( x 1 ) 0 ( m o d p ) p(x-1) \equiv 0 \pmod{p} , p ( x 1 ) + 1 1 ( m o d p ) p(x-1) + 1\equiv 1 \pmod{p} , ... , p x 1 p 1 ( m o d p ) px-1 \equiv p-1 \pmod{p} . Therefore the terms on the numerator form the full set of residues modulo p p . Cancelling through gives us p ( x 1 ) × ( p 1 ) ! p ! p ( x 1 ) p x 1 ( m o d p ) \dfrac{p(x-1) \times (p-1)!}{p!} \equiv \dfrac{p(x-1)}{p} \equiv x-1 \pmod{p} Now consider the second term. x ( p 1 ) x p 1 < x p x(p-1) \le xp-1 < xp . Therefore x p 1 x = p 1 \lfloor \dfrac{xp-1}{x} \rfloor = p-1 . So now plugging these into the congruence we get that ( x p 1 p ) x p 1 x x 1 ( p 1 ) x ( m o d p ) \dbinom{xp-1}{p} - \lfloor \dfrac{xp-1}{x} \rfloor \equiv x-1-(p-1) \equiv x \pmod{p} But we have that x x is ranging over the positive multiples of p p , so x 0 ( m o d p ) x \equiv 0 \pmod{p} . Therefore the only valid value of r r is 0, so there is 1 \fbox{1} value

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...