Click here to Skip to main content
12,952,398 members (46,449 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


1 bookmarked
Posted 8 Aug 2012

Not so many irreducible fractions

, 8 Aug 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
A solution to a Math problem.

I accidently found few papers in my parents' house, dating since I was 15 (I have no idea how those papers survived almost 19 years, but I am glad I found them). Those days, I was involved in Mathematical Olympiads, at school and national level. As you can imagine, those papers contain problems :)

This post is dedicated to one particular problem, that is:

Prove that any arbitrary segment of size 1⁄n (n >1, n∈N) on ℜ contains no more than (n+1)⁄2 irreducible fractions of type p⁄q (p,q∈Z), where 1≤q≤n.

What I remember, so far, is that this problem was part of the Liouville numbers lesson. Unfortunately, I can't reproduce the lesson (I can't remember it :(), but ... below is an alternative proof, containing the sort of analysis I like to define as "Don't be lazy to unfold the details".

Let's pick up an arbitrary number α∈ℜ so that it defines the [α, α+1⁄n] segment. For any rational number (irreducible fraction) p⁄q (p,q∈Z, 1≤q≤n) on this segment we have:
α≤p⁄q≤α+1⁄n or


1. Let's consider q=1, then from (*) we have α≤p1≤α+1⁄n. There can be maximum one such integer number p1. Why? Let's suppose there exists another one t1≠p1 so that
But this means 1≤|t1-p1|≤1⁄n<1, which is impossible (absolute difference between 2 different integers is always ≥1).

2. Let's consider q=2, then from (*) we have 2⋅α≤p2≤2⋅α+2⁄n. There can be maximum one such integer number p2 (proof is identical to the case above except 1≤|t2-p2|≤2⁄n).


N-1. Let's consider q=n-1, then from (*) we have (n-1)⋅α≤pn-1≤(n-1)⋅α+(n-1)⁄n. There can be maximum one such integer number pn-1 (proof is identical to the case(s) above except 1≤|tn-1-pn-1|≤(n-1)⁄n).

N. Let's consider q=n, then from (*) we have n⋅α≤p≤n⋅α+1. There can be maximum two (!!!) such integer numbers pn and pn+1. Why? Imagine that n⋅α is an integer, then n⋅α+1 is another different integer. If n⋅α isn't an integer, then there will be maximum one integer satisfying n⋅α≤pn≤n⋅α+1 (e.g. if we suppose there will be 2 integers n⋅α≤pn<t≤n⋅α+1, then 1≤t–pn≤1t=pn+1. Also n⋅α+1 ≤pn+1=t≤n⋅α+1pn+1= n⋅α+1pn= n⋅α so n⋅α is an integer).

At this step we know that there could be maximum (n+1) integers pi, satisfying (*) where 1≤q≤n.

Next, let's consider all the even q between 1 and n-1, e.g. q=2⋅s, then we have from (*)

2⋅s⋅α≤p2⋅s≤2⋅s⋅α+2⋅s⁄n and
s⋅α≤ps≤s⋅α+s⁄n which is ⇔ (multiplying by 2)
from which we can see that:
|p2⋅s-2⋅ps|≤2⋅s⁄n=q⁄n<1p2⋅s=2⋅ps or
pq⁄q=p2⋅s⁄(2⋅s)=ps⁄s or
pq⁄q is reducible.

We can state now that for any even q, pq⁄q is reducible, but there are (n-1)⁄2 even numbers between 1 and n-1. As a result we have maximum (n-1)⁄2 irreducible fractions satisfying:
α≤p⁄q≤α+1⁄n, where 1≤q≤n-1

What about the q=n case?

As we stated in the case N above, there can be maximum two integers (we noted then pn and pn+1) satisfying
if, and only if n⋅α is an integer.

If we consider pn<pn+1 then

From the case 1 above n⋅α≤n⋅p1≤n⋅α+1 or pn≤n⋅p1≤pn+1 which means
pn=n⋅p1 or

As a result, either pn⁄n or pn+1⁄n is further reducible, considering p1 exists. So we can have maximum one irreducible fraction. This means total maximum is 1+(n-1)⁄2=(n+1)⁄2 now.

If p1 doesn't exists (we stated there could be maximum 1), then both pn⁄n and pn+1⁄n can be irreducible, but the q=1 case (case 1) will have to be removed from the previously analysed options so 2-1+(n-1)⁄2=(n+1)⁄2.

One can observe that from the case 1, we can apply this technique (of multiplying) and deduce that pi=i⋅p1, 1≤i≤n-1. Yes, this is true, if we admit there exists p1 at all (this part is very subtle). But even in this particular case, the total is 2 irreducible fractions that is less than (n+1)⁄2 anyway.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Software Developer (Senior) Snappli Ltd.
United Kingdom United Kingdom
My name is Ruslan Ciurca. Currently I am a Software Developer at

You may also be interested in...

Comments and Discussions

-- There are no messages in this forum --
Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170525.1 | Last Updated 8 Aug 2012
Article Copyright 2012 by rtybase
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid