D 4

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

D 4

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 2 Y

Y by Adventure10, Mango247

Let $n$ be a positive integer. Prove that $n$ is prime if and only if ${{n-1}\choose k}\equiv (-1)^{k}\pmod{n}$ for all $k \in \{ 0, 1, \cdots, n-1 \}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7579 posts

ZetaX

#2 h May 25, 2007, 12:24 AM • 2 Y

Y by Adventure10, Mango247

We will regardless use that we can calculate with fractions $\mod n$ as long as the denominator is coprime to $n$ . It's not hard to show that we always can do that.

If $n$ is not prime, let $q<n$ be the smallest prime dividing $n=aq$ :

$\binom{n-1}{q}= \frac{(n-1) \cdot (n-1) \cdot ... \cdot (n-q)}{1 \cdot 2 \cdot ... \cdot q} =$
$= \frac{n-q}{q} \cdot \frac{n-1}{1} \cdot \frac{n-2}{2} \cdot ... \cdot \frac{n-q+1}{q-1} \equiv (a-1) \cdot (-1)^{q-1} \mod n$ .
But $a-1 \not \equiv -1 \mod n$ (this would yield $a \equiv 0 \mod n$ , so $n|a|n$ , wrong).

If $n$ is prime, we do the same calculation to get
$\binom{n-1}{q}= \frac{(n-1) \cdot (n-1) \cdot ... \cdot (n-q)}{1 \cdot 2 \cdot ... \cdot q} =$
$= \frac{n-1}{1} \cdot \frac{n-2}{2} \cdot ... \cdot \frac{n-q+1}{q-1} \cdot \frac{n-q}{q} \equiv (-1)^q \mod n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#3 h Apr 29, 2008, 9:17 PM • 3 Y

Y by AmazingMonkey, Adventure10, Mango247

For a given $n$ , the set of congruences given are equivalent to $1=C(n-1,0)\equiv(-1)^0=1$ and $C(n,i+1)=C(n-1.i)+C(n-1,i+1)\equiv(-1)^i+(-1)^(i+1)=0$ for $0\le i<n-1$ . Thus the condition given is equivalent to $C(n,i)$ being a multiple of $n$ for all $i$ in the range $1\le i\le n-1$ .

If $n$ is prime, then for $1\le i\le n-1$ , $C(n,i)=n!/i!(n-i)!$ has a multple of $p$ on the numerator but not on the denominator, so is divisible by $p$ .

Now suppose $p$ is a prime factor of $n$ but $n$ is not equal to $p$ . Then $C(n,p)/n=(n-1)(n-2)...(n-(p-1))/p!$ has a multiple of $p$ on the denominator but not on the numerator, so is not an integer. Thus $C(n,p)$ is not divisible by $n$ .

Luke
See my puzzle blog at http://bozzball.blogspot.com

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

548 posts

#4 h Dec 21, 2021, 5:43 AM

Y by

ZetaX very nice solution
.man ham shunday ishladim bosing brat.

This post has been edited 1 time. Last edited by lazizbek42, Dec 21, 2021, 5:44 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a