A 47

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

A 47

G H J

Reveal topic tags

Divisibility Theory

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 • 1 Y

Y by Adventure10

Let $n$ be a positive integer with $n>1$ . Prove that $\frac{1}{2}+\cdots+\frac{1}{n}$ is not an integer.

Z K Y

The post below has been deleted. Click to close.

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

3615 posts

Peter

#2 h Jul 25, 2007, 5:46 PM • 5 Y

Y by SMOJ, HK_Nguyen, brokendiamond, Adventure10, Mango247

nicetry007 wrote:

Let $2^{k}\;\leq \; n \;<\; 2^{k+1}$ .

It is to be noted that every number $m \;\neq\; 2^{k}$ and $m \;\leq\;n$ has a power of $2$ strictly smaller than $k$ .

Suppose not. Let $m \; = \; 2^{l}\cdot s$ where $l \;\geq \;k$ and $s$ is odd and $s \;\geq\; 1$ .

We have $m \; = \; 2^{l}\cdot s \;\leq \;n\;< \;2^{k+1}\;\Rightarrow s \;< \;2^{k+1-l}\;\leq \; 2\;$ ( as $l \;\geq\; k$ ) $\Rightarrow s = 1$ (as $s$ is odd ) $\Rightarrow m \; = \; 2^{l}\;<\; 2^{k+1}\;\Rightarrow \; l \;\leq \; k$ .

But $l\;\geq \;k$ . Hence, $l \; = \; k \;\Rightarrow \; m \; = \; 2^{k}$ , which is a contradiction as $m \;\neq\; 2^{k}$ .

Thus, we can conclude that every $m \; \neq \; 2^{k}$ and $m \;\leq \; n$ has a power of $2$ strictly smaller than $k$ .

The denominator of the sum is the $lcm(2\;,\;3\;,\;\cdots\;,\;n)$ which has $2^{k}$ as a factor. Thus, when we take the sum of all the unit fractions, the numerator of every fraction other than $\frac{1}{2^{k}}$
gets multiplied by a power of $2$ and the numerator of $\frac{1}{2^{k}}$ gets multiplied by an odd number. Hence, the numerator of the sum of all the fractions is an odd number as $odd+even \; = \; odd$ .

Therefore, the sum can never be an integer as the numerator is odd and the denominator is even.

Z K Y

The post below has been deleted. Click to close.

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

74 posts

aham

#3 h May 18, 2010, 4:13 AM • 2 Y

Y by Adventure10, Mango247

Sorry to revive this but I remember there was a proof using Bertrand's postulate and
factorials , but I can't remember the whole thing .Can anyone post it?

Z K Y

The post below has been deleted. Click to close.

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

3130 posts

#4 h May 18, 2010, 7:39 AM • 2 Y

Y by Adventure10, Mango247

aham wrote:

Sorry to revive this but I remember there was a proof using Bertrand's postulate and
factorials , but I can't remember the whole thing .Can anyone post it?

Consider

$\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=\frac{\frac{n!}{1}+\frac{n!}{2}+\cdots+\frac{n!}{n}}{n!}$

By Bertrand's postulate, there exists a prime $p$ such that $\lfloor{\frac{n}{2}}\rfloor <p<n$

If $2p\le n$ , we have $\lfloor{\frac{n}{2}}\rfloor\:<p \le \frac{n}{2}$ which is a clear contradiction.

So, $2p>n$

Or in other words, $p\nmid \frac{n!}{p}$

Now Note that $p|\frac{n!}{k} \forall k \in \mathbb{N}, 1\le k \le n, k\ne p$

So, ${p\nmid \frac{n!}{1}+\frac{n!}{2}+\cdots+\frac{n!}{n}}$ but $p|n!$

$\Longrightarrow \frac{\frac{n!}{1}+\frac{n!}{2}+\cdots+\frac{n!}{n}}{n!}$ is never an integer.

This post has been edited 4 times. Last edited by Goutham, Mar 7, 2012, 2:09 PM

Z K Y

The post below has been deleted. Click to close.

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

798 posts

#5 h May 18, 2010, 2:28 PM • 2 Y

Y by Adventure10, Mango247

gouthamphilomath wrote:

By Bertrand's postulate, there exists a prime $p$ such that $\left\lfloor{\frac{n}{2}}\right\rfloor <p<n$

Be careful! There is no prime $p$ such that $\left\lfloor{\frac{1}{2}}\right\rfloor <p<1$ .

Z K Y

The post below has been deleted. Click to close.

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

122 posts

wood

#6 h May 18, 2010, 3:37 PM • 2 Y

Y by Adventure10, Mango247

Let $p$ be the largest prime among 2,3,....,n. Then by Bertrand's postulate, $p<2n$ . Then we factorize each $m\in [2,n]$ as a product of prime numbers: $m=p_1p_2\cdots p_r$ (here the $p_i$ may duplicate); then $p$ appears in the factorizations only once (when we factorize $p$ itself). Let $p_1,p_2,\cdots,p_k$ be all the prime numbers between 2 and n, excluding the aformentioned $p$ . Then we multiply $\frac 12+\frac 13+\cdots+\frac 1n$ with $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ , and we raise the powers $e_i$ large enough to make $\frac 1m p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ an integer for all $m\neq p$ . But $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\frac 1p$ is not an integer! So comes the conclusion.

Z K Y

The post below has been deleted. Click to close.

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

3130 posts

#7 h May 18, 2010, 4:37 PM • 2 Y

Y by Adventure10, Mango247

MeKnowsNothing wrote:

gouthamphilomath wrote:

By Bertrand's postulate, there exists a prime $p$ such that $\left\lfloor{\frac{n}{2}}\right\rfloor <p<n$

Be careful! There is no prime $p$ such that $\left\lfloor{\frac{1}{2}}\right\rfloor <p<1$ .

To apply Bertrand's postulate, $n \ge 7$ the others are trivial.

Z K Y

The post below has been deleted. Click to close.

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

2663 posts

SMOJ

#8 h Jan 31, 2014, 7:35 AM • 2 Y

Y by Adventure10, Mango247

bobthesmartypants wrote:

Suppose that the numerator when simplified is even. This means that the denominator is odd. This can only happen if no fraction in the original list of fractions that are added has an even denominator; this means that the list of fractions added must be a single fraction $\dfrac{1}{a}$ where $a$ is an odd number. However, the numerator would be $1$ which is odd, so we are done.

Z K Y

The post below has been deleted. Click to close.

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

bobthesmartypants

4337 posts

bobthesmartypants

#9 h Feb 2, 2014, 7:58 PM • 2 Y

Y by Adventure10, Mango247

I proved that the numerator must be odd for any sum $\dfrac{1}{a_1}+\dfrac{1}{a_2}+\cdots +\dfrac{1}{a_n}$ for consecutive integers $a_1,a_2,\cdots a_n$ . However, I don't see how this can immediately be applied to this problem.

Z K Y

The post below has been deleted. Click to close.

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

2663 posts

SMOJ

#10 h Feb 3, 2014, 3:01 AM • 1 Y

Y by Adventure10

Well, we have to use nicetry007's proof for the denominator to be even?

Z K Y

The post below has been deleted. Click to close.

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

769 posts

#11 h Aug 24, 2016, 11:52 AM • 2 Y

Y by Adventure10, Mango247

By Bertrand's postulate,there exists a prime $p$ such that $\lfloor \frac{n}{2}\rfloor <p\le 2\lfloor \frac{n}{2}\rfloor\le n$ .If $2p\le n$ ,then $\lfloor \frac{n}{2}\rfloor <p\le \frac{n}{2}$ which is absurd.Thus if $2\le k\le n$ and $k\neq p$ ,then $p\nmid k$ .So ∃ $a,b\in \mathbb N,p\nmid a$ s.t. $\sum_{k=2,k\neq p}^{n}\frac{1}{k}=\frac{b}{a}$ . Then
$\sum_{k=2}^{n}\frac{1}{k}=\frac{b}{a}+\frac{1}{p}=\frac{pb+a}{pa}$ .
Since $p\nmid pb+a$ , $\frac{pb+a}{pa}$ isn't positive integer.Therefore the proof is completed. $\blacksquare$

This post has been edited 3 times. Last edited by Takeya.O, Aug 24, 2016, 12:13 PM
Reason: adding explanation

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a