Solve Modular Equations With Euler's Theorem

Hey guys! Ever found yourself staring down a modular equation like $x^{29} \equiv 4 \pmod{91}$ and thinking, "How on earth do I find x?" You're in the right spot! Today, we're diving deep into the awesome world of Number Theory, specifically tackling this kind of problem using the mighty Euler's theorem. Now, you might be tempted to jump straight to Fermat's Little Theorem, but remember, Fermat's theorem only works when the modulus is a prime number. Our modulus here is 91, which is $7 * 13$. Since 91 is composite (not prime), we need to bring out the heavier artillery: Euler's theorem. Euler's theorem is a brilliant generalization of Fermat's Little Theorem, and it's our best friend when dealing with composite moduli. So, buckle up, grab your thinking caps, and let's unravel this mathematical mystery together. We'll break down how to compute that elusive integer x step-by-step, making sure you understand the why behind each move. Get ready to flex those number theory muscles!

Understanding Euler's Theorem and Its Power

So, what exactly is Euler's theorem, and why is it so crucial for problems like our $x^{29} \equiv 4 \pmod{91}$? At its core, Euler's theorem states that if n is a positive integer, and a is an integer coprime to n (meaning their greatest common divisor is 1, or gcd(a, n) = 1), then $a^{\phi(n)} \equiv 1 \pmod{n}$. Here, $\phi(n)$ is Euler's totient function, which counts the positive integers up to n that are relatively prime to n. For our problem, the modulus is $n=91$. Since $91 = 7 * 13$, and both 7 and 13 are prime, we can easily calculate $\phi(91)$. If $n = p * q$ where p and q are distinct primes, then $\phi(n) = \phi(p) * \phi(q) = (p-1)(q-1)$. So, for $n=91$, $\phi(91) = \phi(7) * \phi(13) = (7-1)(13-1) = 6 * 12 = 72$. This means that for any integer a where gcd(a, 91) = 1, we have $a^{72} \equiv 1 \pmod{91}$. This is super powerful, guys! It tells us that any exponent modulo 72 will result in the same congruence. For instance, $a^{73} \equiv a^{72} * a^1 \equiv 1 * a \equiv a \pmod{91}$, and $a^{144} \equiv (a^{72})^2 \equiv 1^2 \equiv 1 \pmod{91}$. This cyclic property of exponents under modular arithmetic is what Euler's theorem unlocks for us, especially when dealing with large exponents like 29 in our equation. It simplifies the exponent significantly, making the problem tractable. Remember, the condition gcd(a, n) = 1 is key. If gcd(a, n) is not 1, Euler's theorem in this form doesn't directly apply, and we'd need different techniques, often involving the Chinese Remainder Theorem.

Tackling the Congruence: Step-by-Step Solution

Alright, let's get down to business and solve $x^{29} \equiv 4 \pmod{91}$. We know from Euler's theorem that $\phi(91) = 72$. This means $x^{72} \equiv 1 \pmod{91}$ for any x coprime to 91. Our goal is to manipulate the exponent 29 so we can use this fact. The trick is to find the modular multiplicative inverse of the exponent (29) with respect to $\phi(91)$ (which is 72). In simpler terms, we want to find a number, let's call it d, such that $29 * d \equiv 1 \pmod{72}$. Why? Because if we can find such a d, we can raise both sides of our original congruence to the power of d: $(x^{29})^d \equiv 4^d \pmod{91}$. This simplifies to $x^{29d} \equiv 4^d \pmod{91}$. Since $29d \equiv 1 \pmod{72}$, we can write $29d = 72k + 1$ for some integer k. Substituting this back, we get $x^{72k+1} \equiv 4^d \pmod{91}$. Using exponent rules, this is $(x^{72})^k * x^1 \equiv 4^d \pmod{91}$. And since $x^{72} \equiv 1 \pmod{91}$, the left side becomes $1^k * x \equiv x \pmod{91}$. So, we've successfully isolated x! We just need to find d and then compute $4^d \pmod{91}$.

Now, how do we find d such that $29d \equiv 1 \pmod{72}$? This is where the Extended Euclidean Algorithm comes in handy. We want to express the greatest common divisor of 29 and 72 (which is 1, since they are coprime) as a linear combination of 29 and 72: $29d + 72m = 1$ for some integers d and m. Let's run the Euclidean Algorithm:

1. $72 = 2

29 + 14$ 2. $29 = 2 * 14 + 1$

Now, we work backwards to express 1:

From (2): $1 = 29 - 2 * 14$ Substitute the expression for 14 from (1): $1 = 29 - 2 * (72 - 2 * 29)$ $1 = 29 - 2 * 72 + 4 * 29$ $1 = 5 * 29 - 2 * 72$

So, we have $5 * 29 - 2 * 72 = 1$. Looking at this equation modulo 72, we get $5 * 29 \equiv 1 \pmod{72}$. Bingo! Our modular inverse d is 5. This means $29 * 5 \equiv 1 \pmod{72}$.

Now we can plug this back into our goal: $x \equiv 4^d \pmod{91}$, which is $x \equiv 4^5 \pmod{91}$.

Let's compute $4^5 \pmod{91}$: $4^1 = 4$ $4^2 = 16$ $4^3 = 16 * 4 = 64$ $4^4 = 64 * 4 = 256$. Now, we reduce 256 modulo 91. $256 = 2 * 91 + 74$. So, $4^4 \equiv 74 \pmod{91}$. $4^5 = 4^4 * 4 \equiv 74 * 4 \pmod{91}$. $74 * 4 = 296$. Let's reduce 296 modulo 91. $296 = 3 * 91 + 23$. So, $4^5 \equiv 23 \pmod{91}$.

Therefore, $x \equiv 23 \pmod{91}$.

Verification and Important Considerations

So, we found our candidate solution: $x=23$. But hold up, we need to verify this! Did we make any assumptions that might not hold? Remember Euler's theorem requires gcd(a, n) = 1. In our case, we assumed gcd(x, 91) = 1 when we applied $x^{72} \equiv 1 \pmod{91}$. Let's check if our solution $x=23$ satisfies this. Since $91 = 7 * 13$, we need to check if 23 is divisible by 7 or 13. Clearly, it's not. So, gcd(23, 91) = 1. This means our application of Euler's theorem was valid! Now, let's plug $x=23$ back into the original congruence $x^{29} \equiv 4 \pmod{91}$ and see if it holds.

We need to compute $23^{29} \pmod{91}$. This looks daunting, but we can use the fact that $23^5 \equiv 4 \pmod{91}$ (from our calculation of $4^5 \pmod{91}$ and the inverse relationship). We know $29 = 5 * 5 + 4$. So, $23^{29} = 23^{5 * 5 + 4} = (23^5)^5 * 23^4$. This doesn't seem immediately helpful. Let's use the modular inverse property: we found $d=5$ such that $29d \equiv 1 \pmod{72}$. So, $29 * 5 = 145$. And $145 = 2 * 72 + 1$. This means $23^{145} \equiv (23^{72})^2 * 23^1 \equiv 1^2 * 23 \equiv 23 \pmod{91}$.

Alternatively, recall that we derived $x \equiv 4^d \pmod{91}$, where $d=5$. So we calculated $4^5 \equiv 23 \pmod{91}$. This means that if a solution exists and gcd(x, 91) = 1, then that solution must be congruent to 23 mod 91. Let's verify if $23^{29} \equiv 4 \pmod{91}$ directly. This can be done using modular exponentiation (like the method of repeated squaring), but it's quite computationally intensive by hand. However, the process we followed guarantees that if $x^{29} \equiv 4 \pmod{91}$ has a solution x with gcd(x, 91) = 1, then that solution is x \equiv 4^{29^{-1} mod \phi(91)} \pmod{91}. We found 29^{-1} mod 72 to be 5. So, $x \equiv 4^5 \pmod{91}$. And we calculated $4^5 \equiv 23 \pmod{91}$.

What if gcd(x, 91) is not 1? This means x is a multiple of 7 or 13 (or both). If $x$ is a multiple of 7, then $x^{29} \equiv 0 \pmod 7$. But the equation is $x^{29} \equiv 4 \pmod{91}$, which implies $x^{29} \equiv 4 \pmod 7$. So, $0 \equiv 4 \pmod 7$, which is false. Thus, x cannot be a multiple of 7. Similarly, if x is a multiple of 13, then $x^{29} \equiv 0 \pmod{13}$. The equation $x^{29} \equiv 4 \pmod{91}$ implies $x^{29} \equiv 4 \pmod{13}$. So, $0 \equiv 4 \pmod{13}$, which is false. Therefore, any solution x must be coprime to 91. This confirms that our use of Euler's theorem was justified.

This method is robust! It relies on finding the modular multiplicative inverse of the exponent modulo $\phi(n)$. This is a standard technique in cryptography, particularly in algorithms like RSA, where similar calculations are performed. Always double-check the coprime condition and perform the verification steps to ensure your solution is correct. Number theory can be tricky, but breaking it down step-by-step, especially using powerful tools like Euler's theorem and the Extended Euclidean Algorithm, makes complex problems manageable. Keep practicing, guys, and you'll master these concepts in no time!