Find $6^{273} + 8^{273}\pmod{49}$

Question

The number $6^{273} + 8^{273}$ divided by $49$ has a remainder, what is its value?

I used the totient function to compute for modulo 49. $6^{42}$ and $8^{42}$ are $-1$ and $1$ mod $49$ respectively, $273/49$ is equal to $5$ with a remainder of $21$.

We would then look for the remainder of $-6^{21}$ + $8^{21}$ which I do not know how to solve.

I am aware of other solutions such as factoring odd exponents, but I wanted to know if we can use this kind of approach.

Answer 1

Observe that \begin{align*} 6^{273}+8^{273} & \equiv (7-1)^{273}+(7+1)^{273} \pmod{7^2}\\ & \equiv \sum_{r=0}^{136}\binom{273}{2r}7^{273-2r}\pmod{7^2}\\ & \equiv \binom{273}{272}7\pmod{7^2}\\ & \equiv 7(273) \pmod{7^2}\\ & \equiv 0 \pmod{7^2}. \end{align*}

Answer 2

Note that $6\cdot 8\equiv 48 \equiv -1 \bmod 49$, so $8^{-1}\equiv -6 \bmod 49$.

Then $6^{273}+8^{273} \equiv 6^{273}+(-6)^{-273} \equiv 6^{273} -6^{-273}\bmod 49$ (since $-1^{-1} \equiv -1$)

Since $\phi(49)=42$ Euler gives us $6^{42}\equiv 1\bmod 49$. Then note that $6^{273}\not\equiv 0 \bmod 49$ and $6^{273} (6^{273} -6^{-273}) \equiv 6^{546} -1 \equiv (6^{42})^{13} - 1 \equiv 0 \bmod 49 $ and thus $6^{273} -6^{-273} \equiv 6^{273} + 8^{273} \equiv 0 \bmod 49$

Answer 3

Since $273=7\cdot39$, we see that it's enough to prove that $6^7+8^7$ is divisible by $49$,

which is true because $6+8$ is divisible by $7$ and $$6^6-6^5\cdot8+...+8^6\equiv0(\mod7).$$

Answer 4

Observe that $8^7\equiv1\pmod{49}$. Since $7|273$, so $8^{273}\equiv1\pmod{49}$.

Observe also that $6^7\equiv-1\pmod{49}$. Since $7|273$, so $6^{273}\equiv-1\pmod{49}$.

Adding,$8^{273}+ 6^{273}\equiv0\pmod{49}$.