The floor ⌊x⌋ is the largest integer not above x, and {x}=x−⌊x⌋
Lesson 1 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
work with the floor function and the fractional part, also for negative numbers;
count multiples with ⌊n/d⌋;
prove Legendre's formula and use it for the zeros at the end of n! and for powers of primes in binomial coefficients.
Rounding down
A lift can carry 8 people. How many full trips does it make for 59 people? It makes 7, because 59÷8=7.375, and we drop the part after the point. That is rounding down.
The floor function
The floor of a real number x, written ⌊x⌋, is the largest integer that is not above x. Many Indian books call it the greatest integer function and write [x]. The notation ⌊x⌋ is used in most olympiad and university books.
⌊3.7⌋=3 and ⌊5⌋=5.
⌊−3.7⌋=−4, not −3. The floor goes down the number line, to the left.
The fractional part is {x}=x−⌊x⌋, and it always satisfies 0≤{x}<1. So {−3.7}=0.3. The ceiling⌈x⌉ rounds up.
The definition gives one useful inequality:
⌊x⌋≤x<⌊x⌋+1.
Rules of the floor
⌊x+n⌋=⌊x⌋+n for every integer n.
⌊x⌋+⌊y⌋≤⌊x+y⌋≤⌊x⌋+⌊y⌋+1.
⌊−x⌋=−⌊x⌋−1 when x is not an integer.
⌊n⌊x⌋⌋=⌊nx⌋ for a positive integer n.
Counting multiples. From 1 to n there are ⌊dn⌋ multiples of d.
Rule 5 links the floor to the division algorithm. If n=dq+r with 0≤r<d, then ⌊n/d⌋=q, and the multiples are d,2d,…,qd.
Hermite's identity. For every real x, ⌊x⌋+⌊x+21⌋=⌊2x⌋. Check it by splitting into {x}<21 and {x}≥21.
Solving an equation with a floor
Solve ⌊x⌋=2x−3.
Name the floor. Let n=⌊x⌋, an integer. Then x=2n+3.
Use the inequality.n≤2n+3<n+1. The left part gives n≤3, and the right part gives n>1.
Read off.n=2 or n=3, so x=2.5 or x=3.
Check.⌊2.5⌋=2=2×2.5−3 and ⌊3⌋=3=2×3−3.
The trick is always the same: give the floor a name, then squeeze it with the inequality.
Legendre's formula
How many times does 2 divide 10!=1×2×⋯×10? Count the factors 2 in each number. The even numbers 2,4,6,8,10 give one each: that is ⌊10/2⌋=5. The multiples of 4, which are 4 and 8, give a second one: ⌊10/4⌋=2. The multiple of 8 gives a third: ⌊10/8⌋=1. In all, 5+2+1=8.
Legendre's formula. For a prime p, the exponent of p in n! is
⌊pn⌋+⌊p2n⌋+⌊p3n⌋+⋯
The sum stops by itself once pk>n.
Proof. A number m≤n with exactly j factors p is a multiple of p,p2,…,pj, and of no higher power. So it is counted once in each of the first j terms: j times in all. Adding over all m gives the total number of factors p in n!. Proof complete.
The zeros at the end of n factorial
A zero at the end of a number is a factor 10=2×5. In n! there are many more factors 2 than factors 5, so the number of zeros is the exponent of 5. For 100!:
⌊5100⌋+⌊25100⌋=20+4=24.
So 100! ends in 24 zeros.
 The multiples of 25 give a second 5 each, which is why the count jumps by two at 25!: 24! ends in 4 zeros and 25! in 6. So no factorial ends in exactly 5 zeros.
There is a second form of the formula. If sp(n) is the sum of the digits of n in base p, the exponent is p−1n−sp(n). For p=2 and n=100, written 1100100 in base 2, it gives 1100−3=97.
Primes in binomial coefficients
Since (n2n)=n!n!(2n)!, the exponent of p in it is the exponent in (2n)! minus twice the exponent in n!. For example, the exponent of 3 in (1530) is (10+3+1)−2(5+1)=2. The German mathematician Ernst Kummer showed that this exponent is the number of carries when you add n+n in base p.
Practise with new numbers
Try it in Python
The program finds the exponent of a prime in n! in two ways and counts the zeros of 100! from its digits.
Common mistakes
The floor of a negative number.⌊−2.3⌋=−3.
Stopping Legendre's sum after one term. Multiples of p2, p3, ... add more.
Counting the factors 2 for the zeros. The factors 5 are fewer, so they decide.
Thinking every number of zeros is possible. Some counts are skipped, at each multiple of 25.
Remember these
⌊x⌋≤x<⌊x⌋+1, and {x}=x−⌊x⌋.
From 1 to n there are ⌊n/d⌋ multiples of d.
Exponent of p in n!: ⌊n/p⌋+⌊n/p2⌋+…
Zeros at the end of n!: the exponent of 5.
Exponent of p in (n2n): the exponent in (2n)! minus twice that in n!.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Find ⌊−4.2⌋, ⌈−4.2⌉ and {−4.2}.
How many zeros are at the end of 60!?
Find the exponent of 3 in 30!.
How many whole numbers from 1 to 700 are multiples of 7 but not of 49?
Solve ⌊2x⌋=5.
References
David M. Burton, Elementary Number Theory, Chapter 6, section 6.3 on the greatest integer function and Legendre's formula.
Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers, Chapter 4, section 4.1 on the greatest integer function.
Enroll free in Factorials, Irrational Numbers, Digits and the Floor Function
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.