Arithmetic billiards

Last updated January 29, 2025

The arithmetic billiard for the numbers 15 and 40: the greatest common divisor is 5, the least common multiple is 120. Arithmetic-billiard-40-15.jpg — The arithmetic billiard for the numbers 15 and 40: the greatest common divisor is 5, the least common multiple is 120.

In recreational mathematics, arithmetic billiards provide a geometrical method to determine the least common multiple (LCM) and the greatest common divisor (GCD) of two natural numbers. It makes use of reflections inside a rectangle that has sides with length of the two given numbers. This is a simple example of trajectory analysis used in dynamical billiards.

Properties

The arithmetic billiard for the numbers 10 and 40. Arithmetic-billiard-40-10.jpg — The arithmetic billiard for the numbers 10 and 40.

Arithmetic billiards is a name given to the process of finding both the LCM and the GCD of two integers using a geometric method. It is named for its similarity to the movement of a billiard ball.^[1]

To create an arithmetic billiard, a rectangle is drawn with a base of the larger number, and height of the smaller number. Beginning in the bottom-left corner at 45° angle, a path is drawn until it hits a side of the rectangle. Every time that the path meets the rectangle's side, it reflects with the same angle (the path makes either a left or a right 90° turn). Eventually (i.e., after a finite number of reflections) the path hits a corner and there it stops.^[1]

When the lines cross each other, the path becomes a zigzag consisting of one or more segments. Else, the path has self-intersections and consists of segments of various lengths in two orthogonal directions. In general, the path is the intersection of the rectangle with a grid of squares (oriented at 45° with respect to the rectangle's sides).^[1]^[2]^[3]

Features

The arithmetic billiard for the numbers 3 and 8: the greatest common divisor is 1, the least common multiple is 24. Arithmetic-billiard-8-3.jpg — The arithmetic billiard for the numbers 3 and 8: the greatest common divisor is 1, the least common multiple is 24.

For the rectangle, shaped similar to a billiard table, we give $a$ and $b$ as the side lengths. This can be divided into $a\cdot b$ unit squares. The least common multiple $\operatorname {lcm} (a,b)$ is the number of unit squares crossed by the arithmetic billiard path or, equivalently, the length of the path divided by ${\sqrt {2}}$ .^[1]

Suppose that none of the two side lengths divide the other. Then the first segment of the arithmetic billiard path contains the point of self-intersection that is closest to the starting point. The greatest common divisor $\gcd(a,b)$ is the number of unit squares crossed by the first segment of the path up to that point of self-intersection. The path goes through each unit square if and only if $a$ and $b$ are coprime integers—they have a GCD of 1.^[3]

The number of bouncing points for the arithmetic billiard path on the two sides of length $a$ equals $(a/\operatorname {gcd} (a,b))-1$ , and similarly $(b/\operatorname {gcd} (a,b))-1$ for the two sides of length $b$ . In particular, if $a$ and $b$ are coprime, then the total number of contact points between the path and the perimeter of the rectangle (i.e., the bouncing points plus starting and ending corner) equals $a+b$ .^[2]^[3]

The ending corner of the path is opposite the starting corner if and only if $a$ and $b$ are exactly divisible by the same power of two (for example, if they are both odd), else it is one of the two adjacent corners, according to whether $a$ or $b$ has more factors than $2$ in its prime factorisation. The path is symmetric if the starting and the ending corner are opposite. The path is point symmetric in conjunction with the center of the rectangle, else it is symmetric with respect to the bisector of the side connecting the starting and the ending corner.^[2]^[3]

The contact points between the arithmetic billiard path and the rectangle perimeter are evenly distributed: the distance along the perimeter (i.e., possibly going around the corner) between two such neighbouring points equals $2\gcd(a,b)$ . Setting coordinates in the rectangle such that the starting point is $(0,0)$ and the opposite corner is $(a,b)$ means that any point on the arithmetic billiard path with integer coordinates has the property that the sum of the coordinates is even (the parity cannot change by moving along diagonals of unit squares). The points of self-intersection of the path, the bouncing points, and the starting and ending corner are exactly the points in the rectangle whose coordinates are multiples of $\gcd(a,b)$ and are such that the sum of the coordinates is an even multiple of $\gcd(a,b)$ .^[2]^[3]

Proof

By reflecting the "billiard table" we can visualize the path as a straight line. In this example, the ratio of the two given numbers is 2/3. Arithmetic-billiard-reflection.jpg — By reflecting the "billiard table" we can visualize the path as a straight line. In this example, the ratio of the two given numbers is 2/3.

There are a few ways to show a proof of arithmetic billiards.

Consider a square with side $\operatorname {lcm} (a,b)$ . By displaying multiple copies of the original rectangle (with mirror symmetry), the arithmetic billiard path can be visualised as a diagonal of that square. In other words, one can think of reflecting the rectangle rather than the path segments.^[4]

It is convenient to rescale the rectangle dividing $a$ and $b$ by their greatest common divisor, an operation that does not alter the path's geometry (e.g., the number of bouncing points).^[5]

The motion of the path is “time reversible”, meaning that, if the path is currently traversing one particular unit square (in a particular direction), then there is absolutely no doubt from which unit square and from which direction it originated.^[6]^[5]

One generalisation

A periodic path in the generalised arithmetic billiard with sides 35 and 14. Arithmetic-billiard-35-14.jpg — A periodic path in the generalised arithmetic billiard with sides 35 and 14.

If one allows the starting point of the path to be any point in the rectangle with integer coordinates, then there are also periodic paths, unless the rectangle sides are coprime. The length of any periodic path equals $2\operatorname {lcm} (a,b)\cdot {\sqrt {2}}$ .

Usage

Both Hugo Steinhaus and Martin Gardner have discussed arithmetic billiards as mathematical puzzles.^[7]^[8] Teachers sometimes use arithmetic billiards to show GCD and LCM. They are sometimes referred to by the name 'Paper Pool' due to a common version of billiards called pool.^[9]^[10] They have been used as a source of questions in mathematical circles.^[6]

External links

A website version drawing the lines themed around billiards

Related Research Articles

In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function whose domain is the set of positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.

In number theory, two integers $a$ and $b$ are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides $a$ does not divide $b$ , and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also $a$ is prime to $b$ or $a$ is coprime with $b$ .

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers $x$ , $y$ , the greatest common divisor of $x$ and $y$ is denoted $. For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4 .$

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a, 0) as 0 for all a, since 0 is the only common multiple of a and 0.

In number theory, a multiplicative function is an arithmetic function f(n) of a positive integer n with the property that f(1) = 1 and $whenever a and b are coprime.$

A Pythagorean triple consists of three positive integers $a$ , $b$ , and $c$ , such that $a 2 + b 2 = c 2$ . Such a triple is commonly written $(a, b, c)$ , a well-known example is $(3, 4, 5)$ . If $(a, b, c)$ is a Pythagorean triple, then so is $(ka, kb, kc)$ for any positive integer $k$ . A triangle whose side lengths are a Pythagorean triple is a right triangle and called a Pythagorean triangle.

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and less than n

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that

In mathematics, the distributive property of binary operations is a generalization of the distributive law, which asserts that the equality $is always true in elementary algebra. For example, in elementary arithmetic, one has Therefore, one would say that multiplication distributes over addition.$

In mathematics, the order of a finite group is the number of its elements. If a group is not finite, one says that its order is infinite. The order of an element of a group is the order of the subgroup generated by the element. If the group operation is denoted as a multiplication, the order of an element $a$ of a group, is thus the smallest positive integer $m$ such that $a m = e$ , where $e$ denotes the identity element of the group, and $a m$ denotes the product of $m$ copies of $a$ . If no such $m$ exists, the order of $a$ is infinite.

In geometry, a Heronian triangle is a triangle whose side lengths $a$ , $b$ , and $c$ and area $A$ are all positive integers. Heronian triangles are named after Heron of Alexandria, based on their relation to Heron's formula which Heron demonstrated with the example triangle of sides $13, 14, 15$ and area $84$ .

<span class="mw-page-title-main">Carmichael function</span> Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael function $λ (n)$ of a positive integer $n$ is the smallest positive integer $m$ such that

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a theorem about polynomials over the integers, or, more generally, over a unique factorization domain. Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials.

In mathematics, a natural number a is a unitary divisor of a number b if a is a divisor of b and if a and $are coprime, having no common factor other than 1. Equivalently, a divisor a of b is a unitary divisor if and only if every prime factor of a has the same multiplicity in a as it has in b .$

In algebra, the greatest common divisor of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

In mathematics, the transposable integers are integers that permute or shift cyclically when they are multiplied by another integer $. Examples are:$

<span class="mw-page-title-main">Integer triangle</span> Triangle with integer side lengths

An integer triangle or integral triangle is a triangle all of whose side lengths are integers. A rational triangle is one whose side lengths are rational numbers; any rational triangle can be rescaled by the lowest common denominator of the sides to obtain a similar integer triangle, so there is a close relationship between integer triangles and rational triangles.

In number theory, a kth root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n; that is, a solution x to the equation $. If k is the smallest such exponent for x, then x is called a primitive k th root of unity modulo n . See modular arithmetic for notation and terminology.$

In general topology and number theory, branches of mathematics, one can define various topologies on the set $of integers or the set of positive integers by taking as a base a suitable collection of arithmetic progressions, sequences of the form or The open sets will then be unions of arithmetic progressions in the collection. Three examples are the Furstenberg topology on, and the Golomb topology and the Kirch topology on . Precise definitions are given below.$

References

1 2 3 4 "Arithmetic billiards | plus.maths.org". plus.maths.org. April 24, 2018.
1 2 3 4 Antonella Perucca; Joe Reguengo De Sousa; Sebastiano Tronto (2022). "Arithmetic billiards". Recreational Mathematics Magazine. 9 (16): 43–54. doi: 10.2478/rmm-2022-0003 .
1 2 3 4 5 Arithmetic Billiards (pdf). University of Luxembourg.
↑ https://orbilu.uni.lu/bitstream/10993/35682/1/perucca-arithmetic-billiards.pdf
1 2 Perucca, Antonella (April 24, 2018). "Arithmetic Billiards". Plus Magazine. University of Cambridge. Retrieved December 23, 2018.
1 2 Tanton, James (2012). Mathematical Galore! The First Five Years of the St. Mark's Institute of Mathematics. The Mathematical Association of America. pp. 145–156. ISBN 978-0883857762.
↑ Steinhaus, Hugo (1999). Mathematical Snapshots (Dover Recreational Math Series ed.). Courier Corporation. p. 63. ISBN 0486409147.
↑ Gardner, Martin (1984). Sixth Book of Mathematical Diversions from "Scientific American". University of Chicago Press. pp. 211–215. ISBN 0226282503.
↑ "Paper Pool Game". NCTM Illuminations. National Council of Teachers of Mathematics. Retrieved 10 January 2018.
↑ "Comparing and Scaling: Paper Pool - Connected Mathematics Project".

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[auto-1] 1 2 3 4 "Arithmetic billiards | plus.maths.org". plus.maths.org. April 24, 2018.

[recmaths-2] 1 2 3 4 Antonella Perucca; Joe Reguengo De Sousa; Sebastiano Tronto (2022). "Arithmetic billiards". Recreational Mathematics Magazine. 9 (16): 43–54. doi: 10.2478/rmm-2022-0003 .

[lux-3] 1 2 3 4 5 Arithmetic Billiards (pdf). University of Luxembourg.

[4] ttps://orbilu.uni.lu/bitstream/10993/35682/1/perucca-arithmetic-billiards.pdf

[Perucca-5] 1 2 Perucca, Antonella (April 24, 2018). "Arithmetic Billiards". Plus Magazine. University of Cambridge. Retrieved December 23, 2018.

[Tanton-6] 1 2 Tanton, James (2012). Mathematical Galore! The First Five Years of the St. Mark's Institute of Mathematics. The Mathematical Association of America. pp. 145–156. ISBN 978-0883857762.

[Steinhaus-7] Steinhaus, Hugo (1999). Mathematical Snapshots (Dover Recreational Math Series ed.). Courier Corporation. p. 63. ISBN 0486409147.

[Gardner-8] Gardner, Martin (1984). Sixth Book of Mathematical Diversions from "Scientific American". University of Chicago Press. pp. 211–215. ISBN 0226282503.

[NCTM-9] "Paper Pool Game". NCTM Illuminations. National Council of Teachers of Mathematics. Retrieved 10 January 2018.

[10] "Comparing and Scaling: Paper Pool - Connected Mathematics Project".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]