91Ó°ÊÓ

Fermat's Little Theorem is a powerful tool in number theory that vastly simplifies calculations in modular arithmetic, especially with large exponents. The theorem states that if you have a prime number \( p \) and an integer \( a \) that is not divisible by \( p \), then the formula \( a^{p-1} \equiv 1 \mod p \) holds true.

In simpler terms, if you raise \( a \) to the power of \( p-1 \), the result will always be one when divided by \( p \) (leaving a remainder of one). This theorem is particularly helpful for numbers that would typically be immense to calculate directly.

• Prime number condition: The modulus \( p \) must be prime.
• Non-divisibility condition: \( a \) must not be divisible by \( p \).

In the example \( 2^{100} \mod 11 \), Fermat's Little Theorem comes in handy. Since \( 11 \) is prime and \( 2 \) is not divisible by \( 11 \), we can apply the theorem. This means \( 2^{10} \equiv 1 \mod 11 \), simplifying the original problem significantly. By knowing the cyclicity property defined by the theorem, instead of calculating \( 2^{100} \) directly and then finding its modulus, we use the fact that these powers repeat every ten cycles (as \( 2^{10} \equiv 1 \mod 11 \)).

In mathematics, particularly in number theory, congruences provide a way to compare two numbers regarding their divisibility by a given number, known as the modulus.

Two integers \( a \) and \( b \) are said to be congruent modulo \( n \) if they produce the same remainder when divided by \( n \). This is denoted as \( a \equiv b \mod n \). In essence, congruences show equivalence in terms of remainders:

• If \( a - b \) is divisible by \( n \), then \( a \equiv b \mod n \).
• This property forms a foundational aspect of modular arithmetic.

In the solution to the given exercise, using congruences helps solve \( 2^{100} \mod 11 \) efficiently. By expressing \( 100 \) in terms of a smaller number (as a multiple of the cycle found via Fermat's Little Theorem), we recognize that \( 2^{100} \equiv (2^{10})^{10} \equiv 1^{10} \equiv 1 \mod 11 \). This means that \( 2^{100} \) and \( 1 \) have the same remainder when divided by 11, namely, they are congruent modulo 11.

The modulus is a key concept in modular arithmetic and is essential for understanding how congruences and certain theorems, like Fermat's Little Theorem, function. It is a specific type of calculation that determines the remainder of a division problem.

When performing operations like \( a \mod n \), we determine what is left over after dividing the integer \( a \) by the integer \( n \).

• Example: \( 10 \mod 3 = 1 \) since 10 divided by 3 gives a quotient of 3 with a remainder of 1.
• The modulus operation captures this remainder, essentially a way to "wrap around" number lists after a certain point.

Understanding modulus is crucial in number systems where we "restart" after reaching the modulus value, such as in clocks or cyclic events. In relation to the original problem, using \( \mathbb{Z}_{11} \) means calculating the remainder of numbers when divided by 11. Thus, to solve \( 2^{100} \mod 11 \), it is about finding the remainder of a massive number when divided by 11, guided by Fermat's theorem to make the process feasible.