Problem 6 - An Introduction to Mathematical Cryptography

Question

Let \(a, b, c \in \mathbb{Z}\). Use the definition of divisibility to directly prove the following properties of divisibility. (This is Proposition 1.4.) (a) If \(a \mid b\) and \(b \mid c\), then \(a \mid c\). (b) If \(a \mid b\) and \(b \mid a\), then \(a=\pm b\). (c) If \(a \mid b\) and \(a \mid c\), then \(a \mid(b+c)\) and \(a \mid(b-c)\).

Step-by-Step Solution

Answer

(a) If \(a \mid b\) and \(b \mid c\), then \(a \mid c\). (b) If \(a \mid b\) and \(b \mid a\), then \(a = \pm b\). (c) If \(a \mid b\) and \(a \mid c\), then \(a \mid (b+c)\) and \(a \mid (b-c)\).

Step 1: Understand Divisibility

In number theory, for any integers \(a\) and \(b\), we say \(a\) divides \(b\) (denoted \(a \mid b\)) if there exists an integer \(k\) such that \(b = ak\). This is the definition we'll use to prove the given properties.

Step 2: Prove Part (a) Transitivity

Given \(a \mid b\) and \(b \mid c\), this means there exist integers \(k\) and \(m\) such that \(b = ak\) and \(c = bm\). Substituting for \(b\) in the second equation gives \(c = (ak)m = a(km)\). Since \(km\) is an integer, it follows that \(a \mid c\).

Step 3: Prove Part (b) Mutual Divisibility

Given \(a \mid b\) and \(b \mid a\), there exist integers \(k\) and \(m\) such that \(b = ak\) and \(a = bm\). Substituting \(a = bm\) into \(b = ak\) gives \(b = (bm)k \Rightarrow b = b(mk)\). Nonzero \(b\) implies \(mk = 1\). Consequently, \(m = \pm 1\), leading to \(a = \pm b\).

Step 4: Prove Part (c) Addition and Subtraction Divisibility

Given \(a \mid b\) and \(a \mid c\), there exist integers \(k\) and \(m\) such that \(b = ak\) and \(c = am\). So, \(b + c = ak + am = a(k + m)\), indicating \(a \mid (b + c)\). Similarly, \(b - c = ak - am = a(k - m)\), indicating \(a \mid (b - c)\).

Key Concepts

Number Theory

Number theory is a fascinating area of mathematics that primarily deals with the properties and relationships of integers. It's a foundational topic with various intriguing theorems and concepts. A vital idea in number theory is divisibility, which serves as a building block for many complex theories.
When we talk about divisibility, for any two integers, say \( a \) and \( b \), we say \( a \) divides \( b \) if there exists another integer \( k \) such that \( b = ak \). This means \( b \) can be perfectly divided by \( a \) with no remainder, making \( a \) a divisor of \( b \) and \( b \) a multiple of \( a \).

• This concept extends to various important mathematical areas, including prime numbers, greatest common divisors, and modular arithmetic.
• Divisibility plays a critical role in simplifying proofs and equations within number theory.
• Understanding the definition and applications of divisibility can make number theory both accessible and enjoyable for students.

To use the concept effectively, knowing its application through different properties like transitivity, mutual divisibility, and operations like addition and subtraction is key.

Integer Properties

The properties of integers are essential tools when dealing with divisibility and other number theory aspects. Integers are whole numbers that can be positive, negative, or zero. These basic properties help us understand how integers behave under different mathematical operations, especially when it comes to proofs.
Some of the key integer properties include:

• Transitivity: This property shows that if \( a \mid b \) and \( b \mid c \), then \( a \mid c \). In essence, divisibility is preserved through a chain of integers.
• Mutual Divisibility: When \( a \mid b \) and \( b \mid a \), it implies that the two integers are, apart from sign difference, equal to one another, i.e., \( a = \pm b \).
• Additive and Subtractive Divisibility: If an integer \( a \) divides two other integers \( b \) and \( c \), it also divides their sum and difference, meaning \( a \mid (b+c) \) and \( a \mid (b-c) \).

These properties are grounded on the straightforward nature of integers and their divisibility, making them crucial elements in constructing mathematical arguments and proofs.

Proposition Proof

Proving propositions in number theory requires a strong understanding of the underlying concepts, particularly those related to divisibility. Let's delve into the approach typically used for proofs in this context.
Firstly, when asked to prove properties of divisibility, relying on its definition is crucial. As previously mentioned, \( a \mid b \) if there exists an integer \( k \) such that \( b = ak \). Using this definition helps form a logical argument.

• Example for Transitivity: Given \( a \mid b \) and \( b \mid c \), so \( b = ak \) and \( c = bm \). Substituting gives \( c = a(km) \), showing \( a \mid c \) since \( km \) is an integer.
• Example for Mutual Divisibility: If \( a \mid b \) and \( b \mid a \), then both can be expressed as multiple of some integers. Following logical steps leads you to conclude \( mk = 1 \), showing \( a = \pm b \).
• Example for Addition and Subtraction: Given \( a \mid b \) and \( a \mid c \) implies both can be represented as multiples of \( a \). Therefore, their sum and difference are also multiples of \( a \).

Proving propositions often involves methodical thinking and the ability to connect definitions with logical conclusions. Understanding these steps and their underlying reasons can significantly demystify complex proofs, encouraging deeper exploration of number theory.