A number theory problem by Shikhar Gupta

67 = -1(mod68)

67² = 1(mod68)

67^66 = 1(mod68)

67^67 = 67(mod68)

67^67 +67 = 67+67(mod67)

So, 67^67 + 67 = 66(mod67)

Relevant wiki: Euler's Theorem

$\begin{aligned} 67^{67} + 67 & \equiv 67^{\color{#3D99F6}67 \text{ mod }\phi(68)} + 67 \text{ (mod 68)} & \small \color{#3D99F6} \text{As }\gcd(67,68) = 1 \text {, Euler's theorem applies.} \\ & \equiv 67^{\color{#3D99F6}67 \text{ mod }32} + 67 \text{ (mod 68)} & \small \color{#3D99F6} \text {Euler's totient function }\phi(68) = 32 \\ & \equiv 67^{\color{#3D99F6}3} + 67 \text{ (mod 68)} \\ & \equiv (68-1)^3 + 67 \text{ (mod 68)} \\ & \equiv (-1)^3 + 67 \text{ (mod 68)} \\ & \equiv -1 + 67 \text{ (mod 68)} \\ & \equiv \boxed{66} \text{ (mod 68)} \end{aligned}$

Relevant wiki: Binomial Theorem

We have

$\begin{aligned} 67^{67} + 67 &= {(68-1)}^{67} + 67 \\ &= \left[ \dbinom{67}{0} 68^{67} - \dbinom{67}{1} 68^{66} + \cdots + \dbinom{67}{k} 68^{67-k} \cdot {(-1)}^k + \cdots + \dbinom{67}{66} 68 - \dbinom{67}{67} \right] + 67 \\ &= 68 \lambda - 1 + 67 \qquad \qquad \qquad \qquad \small\color{#D61F06}{\text{where } \lambda = \dbinom{67}{0} 68^{66} - \dbinom{67}{1} 68^{65} + \cdots + \dbinom{67}{66} } \\ &= 68 \lambda + 66 \end{aligned}$

Thus

$68 \lambda + 66 \equiv \boxed{66} \pmod{68}$

Algebra Solution:

Given expression can be written as $67^{67} + 1 + 66$ $\Longrightarrow67^{67} + 1^{67} + 66$

As $\large x^n$ + $\large y^n$ is divisible by $\large x$ + $\large y$ for odd values of $\large n$

Therefore $67^{67} + 1^{67}$ is divisible by 68, leaving 66 as remainder.