MathLinks :: View topic

Art of Problem Solving \| News \| Galleries \| Blogs \| About \| Home
	$LaTeX Help$

Advanced Section

College Playground

International Mathematical Olympiad

National Forums

Galleries

Memberlist

Usergroups

The time now is Sat Nov 21, 2009 12:24 am
All times are UTC + 2

View posts since last visit
View unanswered posts

A 13

Post new topic Reply to topic

Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory

2 Posts • Page 1 of 1

Author

Message

Peter
Birch & Swinnerton Dyer

Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent

A 13
AMM, Problem E2510, Saul Singer

Show that for all prime numbers $p$ , $Q(p)=\prod^{p-1}_{k=1}k^{2k-p-1}$ is an integer.

Posted: Fri May 25, 2007 2:24 am

Profile PM WWW Album

Peter
Birch & Swinnerton Dyer

Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent

nicetry007 wrote:

For $p = 2$ , it is trivially true. Let $p \;\geq\; 3$ .

$Q(p) = \prod_{i = 1}^{p - 1}k^{2k - p - 1} = \left( \frac {\prod_{i = 1}^{p - 1}k^{k}}{\left( (p - 1)! \right)^{(p + 1)/2}}\r...$

It is enough to show that the term inside the parenthesis is an integer.

Let $q$ be a prime less than $p$ . The exponent of $q$ in the denominator is given by

$\frac {(p + 1)}{2}\left (\lfloor\frac {p - 1}{q}\rfloor + \lfloor\frac {p - 1}{q^{2}}\rfloor + \cdots + \lfloor\frac {p - 1}{...$

In the numerator, the terms that are multiples of $q$ are as follows:

$q^{q}, (2q)^{2q}, \cdots, \left( \lfloor\frac {p - 1}{q}\rfloor q \right)^{\lfloor\frac {p - 1}{q}\rfloor q}$

Factoring out a $q$ from all these terms gives us

$q^{(q + 2q + \cdots + \lfloor\frac {p - 1}{q}\rfloor q )} = q^{\frac {q}{2}\lfloor\frac {(p - 1)}{q}\rfloor \left( \lfloor\fr...$

In all, there are $\lfloor\frac {p - 1}{q}\rfloor$ multiples of $q$ in the numerator. Of these $\lfloor\frac {p - 1}{q^{2}}\rfloor$ are multiples of $q^{2}$ .

Factoring out a $q$ from these terms gives us

$q^{(q^{2} + 2q^{2} + \cdots + \lfloor\frac {p - 1}{q^{2}}\rfloor q^{2})} = q^{\frac {q^{2}}{2}\lfloor\frac {p - 1}{q^{2}}\rfl...$ .

Continuing in this fashion, we can compute the exponent of $q$ in the numerator as follows:

$\frac {q}{2}\lfloor\frac {p - 1}{q}\rfloor \left( \lfloor\frac {p - 1}{q}\rfloor + 1 \right) + \frac {q^{2}}{2}\lfloor\frac {...$ .

Comparing the exponent of $q$ in the numerator and the denominator , it suffices to show

$\frac {(p + 1)}{2}\left(\lfloor\frac {p - 1}{q^{i}}\rfloor \right) \leq \frac {q^{i}}{2}\lfloor\frac {p - 1}{q^{i}}\rfloor \l...$ .

It is enough to show

$(p + 1) \leq q^{i}\left( \lfloor\frac {p - 1}{q^{i}}\rfloor + 1 \right) \;\text{\;(i.e.)\;}\; \frac {(p + 1)}{q^{i}}\leq \lfl...$ .

Suppose $q^{i}$ divides $p + 1$ . Then $\lfloor\frac {p - 1}{q^{i}}\rfloor = \frac {(p + 1)}{q^{i}} - 1 (i.e.) \frac {(p + 1)}{q^{i}} = \lfloor\frac {p - 1}{q^{i}}\r...$ .

Suppose $q^{i}$ does not divide $p + 1$ . Then $\lfloor\frac {(p + 1)}{q^{i}}\rfloor = \lfloor \frac {p - 1}{q^{i}}\rfloor$ (i.e.) $\frac {(p + 1)}{q^{i}} = \lfloor\frac {p - 1}{q^{i}}\rfloor + f$ where $f$ is a fraction less than $1$ .
Hence, $\frac {(p + 1)}{q^{i}}\leq \lfloor\frac {p - 1}{q^{i}}\rfloor + 1$ .

Therefore, $Q(p)$ is an integer. In fact, a perfect square.

_________________
Boo!

Posted: Sun Jul 22, 2007 4:25 am

Profile PM WWW Album

2 Posts • Page 1 of 1

Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory

Post new topic Reply to topic

Jump to:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum

Created and Maintained by Valentin Vornicu - (c) AoPS Inc. 2004-2008