Question

The smallest positive integer \(\mathrm{n}\) such that \(11^{\mathrm{n}}-1\) is divisible by 100 is (1) 4 (2) 5 (3) 10 (4) 11

Short answer

10

Step-by-step solution

Identify Euler's Totient Function

We need to find the smallest positive integer \(n\) such that \(11^n - 1\) is divisible by 100. First, determine Euler's Totient function for 100. \[ \phi(100) = \phi(2^2 \times 5^2) = \phi(2^2) \times \phi(5^2) = 4 \times 20 = 40 \] since \( \phi(p^k) = p^k (1 - \frac{1}{p})\).

Find the Order of 11 Modulo 100

Next, find the smallest \(d\) such that \(11^d \equiv 1 \pmod{100}\). We need to determine the order of 11 modulo 100. The positive integer order divides \(\phi(100) = 40\).

Check Divisors of 40

Check the divisors of 40 (1, 2, 4, 5, 8, 10, 20, 40) for the smallest \(d\) that satisfies \(11^d \equiv 1 \pmod{100}\).

Verify 11^4 - 1 Modulo 100

Calculate \(11^4 - 1\) modulo 100: \[ 11^4 = 14641 \rightarrow 14641 - 1 = 14640 \rightarrow 14640 \mod 100 = 40 \] , which is not zero. So, \(d eq 4\).

Verify 11^5 - 1 Modulo 100

Calculate \(11^5 - 1\) modulo 100: \[ 11^5 = 161051 \rightarrow 161051 - 1 = 161050 \rightarrow 161050 \mod 100 = 50 \] , which is not zero. So, \(d eq 5\).

Verify 11^10 - 1 Modulo 100

Calculate \(11^{10} - 1\) modulo 100: \[ 11^{10} = 25937424601 \rightarrow 25937424601 - 1 = 25937424600 \rightarrow 25937424600 \mod 100 = 0 \] This is zero, so \(d = 10\).

Conclusion

The smallest positive integer \(n\) such that \(11^n - 1\) is divisible by 100 is 10.

Key concepts

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers. In this system, numbers wrap around after they reach a certain value, called the modulus. Think of it as a clock. After reaching 12, the clock resets to 1.
For example, in modulo 5 arithmetic, we can say that:

• 7 mod 5 is 2 because when 7 is divided by 5, you get 1 with a remainder of 2.
• Similarly, 14 mod 5 is also 4 because 14 divided by 5 equals 2 with a remainder of 4.

In mathematical notation, if we say a ≡ b (mod n), it means that when a is divided by n, the remainder is b.
This is fundamental in solving problems where we need to find out if certain numbers share properties like divisibility. For instance, determining the smallest positive integer n such that 11^n - 1 is divisible by 100 requires a strong understanding of modular arithmetic.

Positive Integers

Positive integers are all the whole numbers greater than zero, such as 1, 2, 3, etc. They are fundamental in mathematics, forming the basis of arithmetic operations.
In the given problem, we're asked to find the smallest positive integer n for which 11^n - 1 is divisible by 100. Here, 'smallest positive integer' simply means the smallest number greater than 0 that satisfies the condition.
Understanding groups of integers, their properties, and their interactions under various mathematical operations is essential for solving such problems. These integers need to meet specific criteria when explored under modular arithmetic.
For example, whether a positive integer n divides evenly into a number like 100 without leaving a remainder is a core aspect of the exercise.

Divisibility Rules

Divisibility rules help us determine if one integer divides another without a remainder. They simplify our work by allowing quick checks. For example:

• A number is divisible by 2 if it is even.
• It is divisible by 5 if its last digit is either 0 or 5.
• A number is divisible by 10 if its last digit is 0.

In the context of the given problem, we need to figure out when 11^n - 1 is divisible by 100. To do this, we break down the modular arithmetic properties and check various powers of 11 to see when they reset to 1 modulo 100.
This step-by-step process involves examining different divisors of Euler’s totient function value (which is 40) to see which one results in 11^n - 1 being congruent to 0 modulo 100.

Order of a Number Modulo n

The order of a number modulo n is the smallest positive integer k such that a^k ≡ 1 (mod n). This concept is crucial when dealing with exponentiation under modular constraints.
In our problem, we are interested in finding the order of 11 modulo 100. To find this, we look at the divisors of φ(100), which are 1, 2, 4, 5, 8, 10, 20, and 40.
We then check each divisor to see if raising 11 to that power yields a result that is congruent to 1 modulo 100.

• For instance, raising 11 to the power of 4 doesn't work as 11^4 - 1 = 14640, and 14640 modulo 100 is 40, not 0.
• However, raising 11 to the power of 10 works because 11^10 - 1 = 25937424600, and 25937424600 modulo 100 is 0.

Thus, the order of 11 modulo 100 is 10, which is the smallest positive integer n where this relationship holds true.