Remainder Calculation for \(7^n - 6n\) divided by 36

We are asked to find the remainder when the expression \(7^n - 6n\) is divided by 36, specifically for the case where \(n = 100\). This means we need to compute the value of:

\( (7^{100} - 6 \times 100) \pmod{36} \)

To solve this, we can break it down into two parts: calculating the remainder of \(7^{100}\) and the remainder of \(6 \times 100\) separately, then combining them.

Calculating \(6n \pmod{36}\)

First, let's find the remainder of the term \(6n\) when \(n=100\) is divided by 36.

Calculate the value of \(6n\):

\( 6n = 6 \times 100 = 600 \)

Now, find the remainder when 600 is divided by 36:

\( 600 \div 36 \)

We perform the division: \(600 = 16 \times 36 + 24\).

The remainder is 24.

Therefore, we can write this in terms of modular arithmetic:

\( 6 \times 100 \equiv 24 \pmod{36} \)

Calculating \(7^{100} \pmod{36}\)

Next, we need to find the remainder of \(7^{100}\) when divided by 36.

A useful tool for this is Euler's totient theorem. It states that if the greatest common divisor of \(a\) and \(m\) is 1 (i.e., \(\gcd(a, m) = 1\)), then \(a^{\phi(m)} \equiv 1 \pmod{m}\). Here, \(a=7\) and \(m=36\). Since \(\gcd(7, 36) = 1\), the theorem applies.

First, we need to calculate \(\phi(36)\). The prime factorization of 36 is \(36 = 2^2 \times 3^2\).

The formula for Euler's totient function is \(\phi(m) = m \prod_{p|m} (1 - 1/p)\), where \(p\) are the distinct prime factors of \(m\). Alternatively, if \(m = p_1^{k_1} p_2^{k_2} \dots\), then \(\phi(m) = \phi(p_1^{k_1}) \phi(p_2^{k_2}) \dots\), and \(\phi(p^k) = p^k - p^{k-1}\).

Calculating \(\phi(36)\):

\( \phi(36) = \phi(2^2) \times \phi(3^2) \)

\( \phi(2^2) = 2^2 - 2^1 = 4 - 2 = 2 \)

\( \phi(3^2) = 3^2 - 3^1 = 9 - 3 = 6 \)

So, \( \phi(36) = 2 \times 6 = 12 \)

According to Euler's theorem:

\( 7^{\phi(36)} \equiv 7^{12} \equiv 1 \pmod{36} \)

Now we simplify the exponent 100 using the modulus \(\phi(36)=12\). We divide 100 by 12:

\( 100 = 8 \times 12 + 4 \)

Using this, we can rewrite \(7^{100}\):

\( 7^{100} = 7^{8 \times 12 + 4} = (7^{12})^8 \times 7^4 \pmod{36} \)

Since \(7^{12} \equiv 1 \pmod{36}\), we have:

\( 7^{100} \equiv 1^8 \times 7^4 \equiv 7^4 \pmod{36} \)

Now, we calculate the value of \(7^4 \pmod{36}\) step-by-step:

• \(7^1 \equiv 7 \pmod{36}\)
• \(7^2 = 49\). \(49 \div 36\) gives a remainder of 13. So, \(7^2 \equiv 13 \pmod{36}\).
• \(7^3 = 7^2 \times 7 \equiv 13 \times 7 = 91 \pmod{36}\). \(91 = 2 \times 36 + 19\). So, \(7^3 \equiv 19 \pmod{36}\).
• \(7^4 = 7^3 \times 7 \equiv 19 \times 7 = 133 \pmod{36}\). \(133 = 3 \times 36 + 25\). So, \(7^4 \equiv 25 \pmod{36}\).

Thus, we find that:

\( 7^{100} \equiv 25 \pmod{36} \)

Final Combination

Finally, we combine the results for \(7^{100} \pmod{36}\) and \(6 \times 100 \pmod{36}\) to find the remainder of the original expression.

We need:

\( (7^{100} - 6 \times 100) \pmod{36} \)

Substitute the remainders we calculated:

\( (25 - 24) \pmod{36} \)

\( 1 \pmod{36} \)

The remainder when \(7^{100} - 6 \times 100\) is divided by 36 is 1.