Question

Compute each of the following. Show or explain your work. Do not use a calculator or computer. a. \(15^{96}\) in \(Z_{97}\). b. \(67^{72}\) in \(Z_{73}\). c. \(67^{73}\) in \(Z_{73}\).

Short answer

a. 1; b. 1; c. 67.

Step-by-step solution

Understanding Fermat's Little Theorem

When computing powers of numbers modulo a prime, Fermat's Little Theorem can be helpful. It states that if \(p\) is a prime number, then for any integer \(a\) not divisible by \(p\), \(a^{p-1} \equiv 1 \pmod{p}\). We will use this theorem for calculations in parts a and b.

Calculate \(15^{96} \mod 97\) using Fermat's Little Theorem

Since 97 is a prime number, we apply Fermat's Little Theorem. Here, \(a = 15\) and \(p = 97\). According to the theorem, \(15^{96} \equiv 1 \pmod{97}\). Thus, \(15^{96} \equiv 1\).

Calculate \(67^{72} \mod 73\) using Fermat's Little Theorem

Here, we have \(a = 67\) and \(p = 73\). Fermat's Little Theorem tells us that \(67^{72} \equiv 1 \pmod{73}\). Therefore, \(67^{72} \equiv 1\).

Calculate \(67^{73} \mod 73\)

From Fermat's Little Theorem, we know \(67^{72} \equiv 1 \pmod{73}\). Therefore, \(67^{73} = 67^{72} \times 67 \equiv 1 \times 67 \equiv 67 \pmod{73}\). So, \(67^{73} \equiv 67\).

Key concepts

Number Theory

Number theory is a fascinating branch of mathematics that deals with the properties and relationships of numbers, particularly integers. It is considered one of the oldest disciplines within mathematics and has many subfields, some of which include algebraic number theory and analytic number theory.
Here are a few components that define number theory:

• Prime Numbers: These are numbers greater than 1 that have no positive divisors other than 1 and themselves. Prime numbers are crucial in number theory because they act as the building blocks for all natural numbers.
• Divisibility: This refers to the ability of one integer to be divided by another integer without leaving a remainder. Understanding divisibility rules is crucial for computing powers of numbers like in Fermat's Little Theorem.
• Congruences: These are expressions that reflect a form of equality for integers. If two numbers have the same remainder when divided by a third number (called modulus), they are said to be congruent modulo that number.

Number theory is not merely theoretical; it has significant applications in computer science, cryptography, and coding theory.

Modulo Arithmetic

Modulo arithmetic, also known as modular arithmetic, involves integers and a modulus to form a system where numbers "wrap around" upon reaching the modulus value. It is a key concept in number theory, especially when dealing with divisibility.In a mod operation, when a number is divided by the modulus, the remainder is the key outcome:

• Notation: The expression "a mod n" denotes the remainder of the division of a by n, usually written as \(a \equiv r \pmod{n}\) where \(r\) is the remainder.
• Properties: Modular arithmetic possess several unique properties such as if \(a \equiv b \pmod{n}\) and \(c \equiv d \pmod{n}\), then: \(a + c \equiv b + d \pmod{n}\) and \(a \times c \equiv b \times d \pmod{n}\).

Modulo arithmetic is instrumental in simplifying calculations involving exponentiation, which is evident when using Fermat's Little Theorem for reducing large powers to a simple congruence context. This helps in solving equations within a finite number set, making calculations more manageable.

Prime Numbers

Prime numbers play a pivotal role in mathematics, particularly in number theory and modulo arithmetic. A prime number is defined as a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
Prime numbers are fundamental because of the following reasons:

• Building Blocks: Every natural number greater than 1 can be uniquely expressed as a product of prime numbers, known as its prime factorization. This property makes primes the "building blocks" of all whole numbers.
• Relation to Modulo Arithmetic: Many theorems, including Fermat's Little Theorem, rely on the properties of prime numbers. Fermat's theorem discusses the congruence of powers of a number with respect to a prime modulus.
• Applications: Prime numbers are extensively used in cryptography, especially in algorithms such as RSA, where two large prime numbers create a secure key pair for encryption and decryption.

Understanding prime numbers is crucial for grasping advanced concepts in mathematics and for practical applications in technology and security.