Question

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

Short answer

10

Step-by-step solution

- Understand the Problem

We need to find the smallest positive integer \( n \) such that \( 11^n - 1 \) is divisible by 100.

- Factorize the Divisor

Factorize 100 to its prime factors: \( 100 = 2^2 \times 5^2 \). Therefore, \( 11^n - 1 \) must be divisible by both \( 4 \) and \( 25 \).

- Use Euler's Theorem for Divisibility by 4

Euler's theorem states that for any integer \( a \) and \( n \) coprime, \( a^{\phi(n)} \equiv 1 \ (\text{mod} \ n) \), where \( \phi \) is the totient function. Since \( 4 = 2^2 \), and \( \phi(4) = 2 \), it follows that \( 11^2 \equiv 1 \ (\text{mod} \ 4)\). Thus, \( 11^n - 1 \) is divisible by 4 for any even \( n \).

- Use Euler's Theorem for Divisibility by 25

\( 25 = 5^2 \) and \( \phi(25) = 20 \). Therefore, \( 11^{20} \equiv 1 \ (\text{mod} \ 25)\). However, we need a smaller n such that \( 11^n \equiv 1 \ (\text{mod} \ 25) \). Through trial, find that \( 11^5 \equiv 1 \ (\text{mod} \ 25) \).

- Combine Conditions

We need \( n \) to be the smallest number satisfying both conditions from steps 3 and 4. The smallest \( n \) is 10 because it is the least common multiple of the exponents (2 and 5).

Key concepts

Euler's theorem

Euler's theorem is a key concept in number theory. It states that for any integers\(a\)and\(n\)coprime (i.e., they have no common factors other than 1), it follows that: \[a^{\totient(n)} \equiv 1 \pmod{n}\].
Here,\( \totient\) is Euler’s Totient function, which counts the number of positive integers up to\(n\) that are coprime with\(n\). For example,\( \totient(4) = 2\) because the numbers 1 and 3 are the only integers less than 4 that are coprime with 4.
Let’s break down our problem using Euler's theorem. For divisibility by 4, we see that since
\( \totient(4) = 2\), thus\( 11^2 \equiv 1 \pmod{4}\).
This means that any integer\(n\)that is even will satisfy\(11^n - 1\)being divisible by 4. Understanding this simplification helps solve more complex divisibility problems efficiently.

totient function

The totient function, often denoted as\( \totient(n)\), is a way to count the positive integers up to\(n\)that are coprime with\(n\). To calculate\( \totient\)for a number with prime factorization, say\( n = p_1^{k_1} p_2^{k_2} \ldots p_m^{k_m}\), use the formula: \[\totient(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \ldots \left( 1 - \frac{1}{p_m} \right) \].
For instance, for\(25 = 5^2\), the totient function\( \totient(25) = 25 \left(1 - \frac{1}{5} \right) = 25 \left( \frac{4}{5} \right) = 20\).
The relevance of the totient function in problems like ours, lies in Euler’s theorem. Since\( \totient(25) = 20\), Euler's theorem guarantees that\( 11^{20} \equiv 1 \pmod{25}\).
This insight significantly narrows down guesses for smaller values of\(n\), instead of trial and error from scratch.

least common multiple

The least common multiple (LCM) of two integers is the smallest positive integer that is divisible by both. In our problem:
- We found that any even\(n\) ensures\( 11^n - 1\)is divisible by 4.
- We also saw that every multiple of 5 makes\( 11^n\equiv 1 \pmod{25}\). To satisfy both conditions simultaneously, we use the least common multiple.
The LCM of the exponents 2 and 5 is 10. This means the smallest\(n\)ensuring\(11^n - 1\)is divisible by both 4 and 25 is 10.
Thus, based on the least common multiple concept,\(n = 10\)is the smallest integer that fits our divisibility criteria.