Problem 5 - A Computational Introduction to Number Theory and Algebra

Question

Let \(x \in \mathbb{R}\) and \(n \in \mathbb{Z}\) with \(n>0 .\) Show that \(\lfloor\lfloor x\rfloor / n\rfloor=\lfloor x / n\rfloor ;\) in particular, \(\lfloor\lfloor a / b\rfloor / c\rfloor=\lfloor a / b c\rfloor\) for all positive integers \(a, b, c .\)

Step-by-Step Solution

Answer

Question: Prove that \(\lfloor\lfloor x\rfloor / n\rfloor=\lfloor x / n\rfloor\) for all real numbers \(x\) and positive integers \(n\), and show that as a particular case, \(\lfloor\lfloor a / b\rfloor / c\rfloor=\lfloor a / bc\rfloor\) for all positive integers \(a, b, c\) . Answer: We proved that \(\lfloor\lfloor x\rfloor / n\rfloor=\lfloor x / n\rfloor\) for all real numbers \(x\) and positive integers \(n\) by simplifying both expressions to the quotient \(q\) of \(x\) and \(n\). As a particular case, we showed that \(\lfloor\lfloor a / b\rfloor / c\rfloor=\lfloor a / bc\rfloor\) for all positive integers \(a, b, c\), directly from the general result.

Step 1: Define the floor function

The floor function, denoted by \(\lfloor x\rfloor\), is a function that takes a real number \(x\) as its input and returns the greatest integer less than or equal to \(x\). For example, \(\lfloor 2.7\rfloor = 2\), \(\lfloor -1.2\rfloor = -2\), and \(\lfloor 3\rfloor = 3\).

Step 2: Use the properties of the floor function

Let \(x = nq + r\), where \(q\) is \(\lfloor\frac{x}{n}\rfloor\) (the quotient) and \(0 \leq r < n\). So, \(\lfloor x\rfloor = \lfloor nq + r\rfloor\). Note that \(0 \leq r < n \implies -n < -r \leq 0\). So, we have \(0 \leq nq-r < n\).

Step 3: Find the greatest integer less than or equal to \(x - r\)

Since \(0 \leq nq-r < n\), we can apply the floor function to it. We get $$ \lfloor nq - r\rfloor = nq. $$ This is because \(nq\) is an integer and it already falls within the range \(0 \leq nq-r < n\).

Step 4: Express \(\lfloor\lfloor x\rfloor / n\rfloor\)

Now, we can express \(\lfloor\lfloor x\rfloor / n\rfloor\) using the information obtained in the previous steps: $$ \lfloor\lfloor x\rfloor / n\rfloor = \lfloor\frac{\lfloor nq + r\rfloor}{n}\rfloor = \lfloor\frac{nq}{n}\rfloor = \lfloor q\rfloor = q. $$

Step 5: Express \(\lfloor x / n\rfloor\)

Using the quotient and remainder from Step 2, we can express \(\lfloor x / n\rfloor\) as: $$ \lfloor x / n\rfloor = q. $$

Step 6: Compare the two expressions

Now we can show that \(\lfloor\lfloor x\rfloor / n\rfloor\) and \(\lfloor x / n\rfloor\) are equal, because both expressions have been simplified to \(q\), the quotient of \(x\) and \(n\). So, we have proved that $$ \lfloor\lfloor x\rfloor / n\rfloor = \lfloor x / n\rfloor. $$

Step 7: Prove the particular case

For the particular case where \(x = a/b\), and positive integers \(a, b, c\) are given, we have $$ \lfloor\lfloor\frac{a}{b}\rfloor / c\rfloor = \lfloor\frac{a}{bc}\rfloor. $$ This follows directly from the general result we just proved, since \(\frac{a}{b}\) is a real number and \(\frac{a}{bc}\) is also a real number. This completes our proof.

Key Concepts

Integer Division

Integer division is a fascinating concept that often trips students up because it deviates from the division taught at earlier levels. In mathematics, integer division involves dividing two integers and returning only the quotient, without the remainder. This means if you divide 7 by 3, instead of getting the exact result of 2.333..., integer division gives you just the integer part: 2.

Here are a few things to remember about integer division:

• When the division is not exact, the result is simply rounded down to the nearest whole number.
• The result is always an integer, even if the input was not evenly divisible.
• Integer division is used in computer programming languages to ensure results remain in integer form, avoiding potential decimal issues.

This operation is closely tied to the floor function, as both seek to provide integer outputs. Understanding integer division is crucial for comprehending topics like the floor function and mathematical proofs that involve real numbers.

Mathematical Proof

A mathematical proof is like a logical puzzle, where the goal is to show why a particular statement must be true using deductive reasoning. Proofs form the backbone of mathematics, helping verify the truth of mathematical claims beyond a doubt.

Here's how a mathematical proof typically unfolds:

• **Initial Assumptions:** Start by assuming what is given or known. In our exercise, this was the understanding of the floor function and real numbers.
• **Logical Steps:** Break down the problem into smaller, manageable parts using logical reasoning. Each step logically follows the previous one.
• **Conclusion:** End with a robust conclusion—showing the final statement must be true, as seen when proving \( \lfloor\lfloor x\rfloor / n\rfloor=\lfloor x / n\rfloor \).

This process helps ensure that statements in mathematics aren't just true at face value but are logically and universally valid. Proofs require a balance of creativity and rigor, helping mathematicians build on existing knowledge.

Real Numbers

Real numbers are the cornerstone of mathematical operations in both theory and application. They encompass all the numbers that can be represented on the number line—ranging from simple integers to complex fractions and irrationals.

Real numbers can be categorized into:

• **Natural Numbers:** Like 1, 2, 3...
• **Whole Numbers:** Natural numbers including 0.
• **Integers:** Negative and positive numbers, including zero.
• **Rational Numbers:** Numbers that can be expressed as a fraction of two integers, where the denominator is not zero.
• **Irrational Numbers:** Numbers that cannot be expressed as a simple fraction, like \( \pi \) or \( \sqrt{2} \).

Understanding where real numbers fit in helps in grasping operations like floor functions and their properties. The floor function takes a real number and returns the greatest integer less than or equal to it, forming a critical link between real numbers and integer mathematics, as seen in the exercise above.