Basic Number Theory - Hoang Anh Duc - MIM - HUS - VNU

Work 2.

\[\begin{align} & \text{Prove that the congruence relation modulo } m \text{ (mod m)} \quad \\[5pt] & \text{is an equivalence relation on the set of integers} \quad \end{align}\]

Solution:

\[\begin{align} & \textbf{1. Reflexivity:} \quad \\[5pt] & \text{For any integer } a, \quad a \equiv a \ (\text{mod} \ m) \text{ since } m \text{ divides } (a - a) = 0. \quad \\[5pt] & \text{Thus, congruence modulo } m \text{ is reflexive.} \quad \\[10pt] & \textbf{2. Symmetry:} \quad \\[5pt] & \text{Suppose } a \equiv b \ (\text{mod} \ m). \text{ Then } m \text{ divides } (a - b). \quad \\[5pt] & \text{This implies that } m \text{ also divides } (b - a), \text{ so } b \equiv a \ (\text{mod} \ m). \quad \\[5pt] & \text{Thus, congruence modulo } m \text{ is symmetric.} \quad \\[10pt] & \textbf{3. Transitivity:} \quad \\[5pt] & \text{Suppose } a \equiv b \ (\text{mod} \ m) \text{ and } b \equiv c \ (\text{mod} \ m). \quad \\[5pt] & \text{Then } m \text{ divides } (a - b) \text{ and } m \text{ divides } (b - c). \quad \\[5pt] & \text{Therefore, } m \text{ divides } (a - b) + (b - c) = a - c, \text{ so } a \equiv c \ (\text{mod} \ m). \quad \\[5pt] & \text{Thus, congruence modulo } m \text{ is transitive.} \quad \\[10pt] & \text{Since the congruence modulo } m \text{ satisfies reflexivity, symmetry,} \quad \\[5pt] & \text{and transitivity, it is an equivalence relation on the set of integers.} \quad \end{align}\]

Work 5.

\[\begin{align} & \text{Prove that the product of any 3 consecutive} \quad \\[5pt] & \text{integers is always devisable by 6} \quad \end{align}\]

Solution:

• Let the three consecutive integers be (n), (n+1), and (n+2). We will show that their product (n(n+1)(n+2)) is always divisible by 6 by proving that it is divisible by both 2 and 3.

\[\begin{align} & \textbf{1. Divisibility by 2:} \quad \\[5pt] & \text{Among any three consecutive integers, at least one of them is even.} \quad \\[5pt] & \text{Thus, } n(n+1)(n+2) \text{ is always divisible by 2.} \quad \\[10pt] & \textbf{2. Divisibility by 3:} \quad \\[5pt] & \text{Among any three consecutive integers, one of them must be divisible by 3.} \quad \\[5pt] & \text{Thus, } n(n+1)(n+2) \text{ is always divisible by 3.} \quad \\[10pt] & \textbf{3. Divisibility by 6:} \quad \\[5pt] & \text{Since } n(n+1)(n+2) \text{ is divisible by both 2 and 3, it is also divisible by 6.} \quad \\[10pt] & \text{Therefore, the product of any 3 consecutive integers is always divisible by 6.} \end{align}\]

Work 6.

\[\begin{align} & \text{Converting a number from decimal to base-n:} \quad \\[5pt] & \quad (1) \quad \text{Find the rightmost digit by calculating } n \text{ mod } b \quad \\[5pt] & \quad (2) \quad \text{Perform assignment } n := n / b \quad \\[5pt] & \quad (3) \quad \text{Repeat (1) and (2) until } n = 0 \quad \\[15pt] & n = bq_0 + a_0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \quad \space \space n := q_0 \quad \\[5pt] & \quad = b(bq_1+a_1)+a_0 \quad \\[5pt] & \quad = b^2q_1+ ba_1+a_0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \space \space n := q_1 \quad \\[5pt] & \quad \vdots \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \vdots \quad \\[5pt] & \quad = b^k(0+a_k)+b^{k-1}a_{k-1}+ \ldots + b^3a_3 + b^2a_2 + ba_1 + a_0 \qquad n := q_1 \quad \\[5pt] & \quad = b^ka_k+b^{k-1}a_{k-1}+ \ldots + b^3a_3 + b^2a_2 + ba_1 + a_0 \quad \\[15pt] & \text{Describe the process above with pseudo code} \end{align}\]

Solution:

def decimal_to_base_n(n: int, b: int) -> str:
    """
    Convert a decimal number to its representation in base b.
    
    Args:
        n: A non-negative integer to convert
        b: The target base (2-36)
        
    Returns:
        A string representation of the number in base b
        
    Raises:
        ValueError: If n is negative or b is not in range [2, 36]
    """
    # Input validation
    if n < 0:
        raise ValueError("Number must be non-negative")
    if b < 2 or b > 36:
        raise ValueError("Base must be between 2 and 36")
    
    # Special case for n = 0
    if n == 0:
        return "0"
    
    # Digits for bases > 10
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    # Initialize result
    result = []
    
    # Continue division until quotient becomes 0
    while n > 0:
        # Find rightmost digit (remainder)
        remainder = n % b
        
        # Convert digit to proper character representation
        result.append(digits[remainder])
        
        # Update n with integer division
        n //= b
    
    # Return the reversed string (since we built it backwards)
    return "".join(reversed(result))

# Example usage and tests
def test_conversions():
    test_cases = [
        (25, 2),    # Binary
        (25, 8),    # Octal
        (25, 16),   # Hexadecimal
        (255, 16),  # Larger hex number
        (1234, 36), # Largest supported base
    ]
    
    for n, b in test_cases:
        result = decimal_to_base_n(n, b)
        print(f"{n} in base-{b} is: {result}")

if __name__ == "__main__":
    test_conversions()
    
    # Output will be:
    # 25 in base-2 is: 11001
    # 25 in base-8 is: 31
    # 25 in base-16 is: 19
    # 255 in base-16 is: FF
    # 1234 in base-36 is: YA

Work 9.

\[\begin{align} & \text{Calculate the following sums and products in binary:} \quad \\[5pt] & (a) \quad (1000111)_2 \text{ and } (1110111)_2 \quad \\[5pt] & \qquad \small\text{Reference: Sum=}(10111110)_2, \text{ Prod=}(10000100000001)_2 \quad \\[5pt] & (b) \quad (11101111)_2 \text{ and } (10111101)_2 \quad \\[5pt] & \qquad \small\text{Reference: Sum=}(110101100)_2, \text{ Prod=}(1011000001110011)_2 \quad \end{align}\]

Solution:

• \((a) \quad (1000111)_2 + (1110111)_2\).

    1111111  ← carries
    1000111
  + 1110111
  ---------
   10111110

• \((a) \quad (1000111)_2 \times (1110111)_2\).

       1000111
    ×  1110111
    -----------
       1000111  ← (1000111 × 1)
      1000111   ← (1000111 × 1)
     1000111    ← (1000111 × 1)
    1000111     ← (1000111 × 1)
   0000000      ← (1000111 × 0)
  1000111       ← (1000111 × 1)
 1000111        ← (1000111 × 1)
 ---------------
 10000100000001

• \((b) \quad (11101111)_2 + (10111101)_2\).

    1111111   ← carries
   11101111
 + 10111101
 -----------
  110101100

• \((b) \quad (11101111)_2 \times (10111101)_2\).

        11101111
     ×  10111101
     -------------
        11101111  ← (11101111 × 1)
       00000000   ← (11101111 × 0)
      11101111    ← (11101111 × 1)
     11101111     ← (11101111 × 1)
    11101111      ← (11101111 × 1)
   11101111       ← (11101111 × 1)
  00000000        ← (11101111 × 0)
 11101111         ← (11101111 × 1)
 -----------------
 1011000001110011

Work 19.

\[\begin{align} & \text{Find the modular multiplicative} \quad \\[5pt] & \text{inverse of a modulo m, where:} \quad \\[8pt] & \quad (1) \quad a = 4, m = 9 \quad \\[5pt] & \quad (2) \quad a = 19, m = 141 \quad \\[5pt] & \quad (3) \quad a = 55, m = 89 \quad \\[5pt] & \quad (4) \quad a = 89, m = 232 \quad \\[5pt] \end{align}\]

Solution:

9 = 4(2) + 1
4 = 4(1) + 0

Working backwards:
1 = 9 - 4(2)
1 = 9(1) + 4(-2)

Therefore: 4(-2) ≡ 1 (mod 9)
Answer: -2 ≡ 7 (mod 9)

141 = 19(7) + 8
19 = 8(2) + 3
8 = 3(2) + 2
3 = 2(1) + 1
2 = 1(2) + 0

Working backwards:
1 = 3 - 2(1)
  = 3 - (8 - 3(2))(1)
  = 3(3) - 8(1)
  = (19 - 8(2))(3) - 8(1)
  = 19(3) - 8(7)
  = 19(3) - (141 - 19(7))(7)
  = 19(52) - 141(7)

Therefore: 19(52) ≡ 1 (mod 141)
Answer: 52

89 = 55(1) + 34
55 = 34(1) + 21
34 = 21(1) + 13
21 = 13(1) + 8
13 = 8(1) + 5
8 = 5(1) + 3
5 = 3(1) + 2
3 = 2(1) + 1
2 = 1(2) + 0

Working backwards:
1 = 3 - 2(1)
  = 3 - (5 - 3(1))(1)
  = 3(2) - 5(1)
  = (8 - 5(1))(2) - 5(1)
  = 8(2) - 5(3)
  = (13 - 8(1))(2) - 5(3)
  = 13(2) - 8(2) - 5(3)
  = 13(2) - (21 - 13(1))(2) - 5(3)
  = 13(4) - 21(2) - 5(3)
  = (34 - 21(1))(4) - 21(2) - 5(3)
  = 34(4) - 21(6) - 5(3)
  = (55 - 34(1))(4) - 21(6) - 5(3)
  = 55(4) - 34(4) - 21(6) - 5(3)
  = (89 - 55(1))(4) - 34(4) - 21(6) - 5(3)
  = 89(4) - 55(8)

Therefore: 55(-8) ≡ 1 (mod 89)
Answer: -8 ≡ 81 (mod 89)

232 = 89(2) + 54
89 = 54(1) + 35
54 = 35(1) + 19
35 = 19(1) + 16
19 = 16(1) + 3
16 = 3(5) + 1
3 = 1(3) + 0

Working backwards:
1 = 16 - 3(5)
  = 16 - (19 - 16(1))(5)
  = 16(6) - 19(5)
  = (35 - 19(1))(6) - 19(5)
  = 35(6) - 19(11)
  = (54 - 35(1))(6) - 19(11)
  = 54(6) - 35(6) - 19(11)
  = (89 - 54(1))(6) - 35(6) - 19(11)
  = 89(6) - 54(12) - 35(6) - 19(11)
  = (232 - 89(2))(6) - 54(12) - 35(6) - 19(11)
  = 232(6) - 89(23)

Therefore: 89(-23) ≡ 1 (mod 232)
Answer: -23 ≡ 209 (mod 232)

Work 24.

\[\begin{align} & \text{Solve the following linear congruences:} \quad \\[8pt] & \quad (1) \quad x \equiv 2 \text{ (mod 3)} \quad \\[5pt] & \quad (2) \quad x \equiv 1 \text{ (mod 4)} \quad \\[5pt] & \quad (3) \quad x \equiv 3 \text{ (mod 5)} \quad \\[5pt] \end{align}\]

Work 30.

\[\begin{align} & (a) \quad \text{Use Fermat's little theorem to calculate:} \quad \\[5pt] & \qquad 5^{2003} \text{ mod } 7, 5^{2003} \text{ mod } 11, 5^{2003} \text{ mod } 13 \quad \\[5pt] & (b) \quad \text{Use Chinese remainder theorem to calculate:} \quad \\[5pt] & \qquad 5^{2003} \text{ mod } 1001 \quad \\[5pt] \end{align}\]