Problem 39 - Abstract Algebra: Theory and Applications

Question

Let \(\operatorname{gcd}(a, n)=d\) and \(\operatorname{gcd}(b, d) \neq 1\). Prove that \(a x \equiv b(\bmod n)\) does not have a solution.

Step-by-Step Solution

Answer

Question: Prove that the linear congruence ax ≡ b (mod n) does not have a solution when gcd(a, n) = d and gcd(b, d) ≠ 1. Answer: In this case, the gcd(b, d) cannot be expressed as an integer combination of a and n, making it impossible to find a solution for the linear congruence ax ≡ b (mod n).

Step 1: Write down the linear congruence

The given linear congruence is \(ax \equiv b \pmod{n}\), we have to prove that there is no solution to this linear congruence when \(\operatorname{gcd}(a, n) = d\) and \(\operatorname{gcd}(b, d) \neq 1\).

Step 2: Use properties of congruences

Since \(ax \equiv b \pmod{n}\), we know that \(n|(ax -b)\). This means that there exists an integer \(k\) such that \(ax - b = nk\).

Step 3: Analyze the given conditions

We have two conditions given: first is \(\operatorname{gcd}(a, n) = d\) and second is \(\operatorname{gcd}(b, d) \neq 1\). As we have the gcd relations, let's rewrite our given equation in terms of \(d\). Since, \(\operatorname{gcd}(a, n) = d\), let \(a = dp\) and \(n = dq\) for some integers \(p\) and \(q\).

Step 4: Substitute the expressions obtained in step 3 into the congruence

Substituting the values obtained in step 3, the equation \(ax - b = nk\) becomes \(dpq \times x - b = d \times q \times k\).

Step 5: Observe that d divides both sides of the equation

From the equation in step 4, we can observe that \(d\) divides both sides of the equation. It also suggests that \(d\) must divide \(b\). That is, \(\operatorname{gcd}(b, d) = d\) instead of 1. This means our given condition, \(\operatorname{gcd}(b, d) \neq 1\) is satisfied.

Step 6: Provide the contradiction and conclude the proof

However, knowing that \(\operatorname{gcd}(b, d) = d\), and neither \(d\) nor \(b\) is 1 (as suggested by our given condition), this implies that \(b\) cannot be expressed as an integer combination of \(a\) and \(n\) (using the properties of gcd). Thus, the equation \(ax ≡ b \pmod{n}\) does not have a solution when \(\operatorname{gcd}(a, n) = d\) and \(\operatorname{gcd}(b, d) \neq 1\). Hence, proved.

Key Concepts

Greatest Common Divisor (GCD)

Understanding the greatest common divisor (GCD) is crucial when dealing with linear congruences. The GCD of two integers, commonly denoted by \(\operatorname{gcd}(a, b)\), is the largest positive integer that divides both \(a\) and \(b\) without leaving a remainder. For instance, the GCD of 8 and 12 is 4.

Properties of GCD that are especially useful in solving congruences include:

• If \(\operatorname{gcd}(a, n) = d\), then \(a\) and \(n\) can be written as \(a=dp\) and \(n=dq\), where \(p\) and \(q\) are integers that have no common divisors other than 1, also known as 'coprime' or 'relatively prime'.
• If \(\operatorname{gcd}(b, d) eq 1\), then \(b\) is not coprime with \(d\) which means, it shares a common divisor greater than 1 with \(d\).

If you're solving a linear congruence and find that \(b\) does not share a GCD of 1 with the GCD of \(a\) and \(n\), this would indicate there is no solution under the standard rules of modular arithmetic.

Properties of Congruences

Congruences have several properties that make them behave somewhat similarly to equations but under the scope of modular arithmetic. Key properties include:

• If \(a \text{ mod } n = b \text{ mod } n\), then \(a\) is said to be congruent to \(b\) modulo \(n\), denoted by \(a \equiv b \pmod{n}\).
• Congruence is transitive: if \(a \equiv b \pmod{n}\) and \(b \equiv c \pmod{n}\), then \(a \equiv c \pmod{n}\).
• If \(a \equiv b \pmod{n}\) and \(c \equiv d \pmod{n}\), then \(a+c \equiv b+d \pmod{n}\) and \(ac \equiv bd \pmod{n}\).

When it comes to solving linear congruences like \(ax \equiv b \pmod{n}\), these properties guide us in manipulating the terms to seek a solution. However, if through manipulation using these properties we encounter a contradiction, it would imply that a solution does not exist for the given congruence.

Modular Arithmetic

Modular arithmetic, often referred to as 'clock arithmetic,' is a system of arithmetic for integers, where numbers 'wrap around' after reaching a certain value—the modulus. The basic idea is that in this system, two numbers are equivalent (or 'congruent') if they have the same remainder when divided by the modulus.

For example, in modulo 5 arithmetic, 7 and 12 are equivalent because they both leave a remainder of 2 when divided by 5.A foundational concept in modular arithmetic is that of congruence, as represented by the equation \(ax \equiv b \pmod{n}\). The arithmetic provides rules and methods for solving such equations but also sets conditions for their solvability. For instance, if the GCD of \(a\) and \(n\) does not equally divide \(b\), no solution exists for the linear congruence.

Integer Combination

An integer combination refers to an expression made up of integers multiplied by other integers and added together. For instance, if \(a\) and \(b\) are integers, and \(x\) and \(y\) are also integers, then \(ax + by\) is an integer combination of \(a\) and \(b\). A notable result in number theory states that the GCD of \(a\) and \(b\) is the smallest positive integer that can be represented as an integer combination of \(a\) and \(b\).

This concept is crucial when dealing with linear congruences as well. Specifically, for the congruence \(ax \equiv b \pmod{n}\) to have a solution, \(b\) must be expressible as an integer combination of \(a\) and \(n\). If not, as with the case when \(\operatorname{gcd}(b, d) eq 1\), there can be no solution.