4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Note, $6^{42}$ and $8^{42}$ are both $\equiv 1 \bmod 49$ as per Euler's theorem $\endgroup$
    – Joffan
    Nov 23, 2017 at 17:39

4 Answers 4

3
$\begingroup$

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*}

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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).$$

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.