# Let $A=3^{105} + 4^{105}$. Show that $7\mid A$. [duplicate]

Let $A=3^{105} + 4^{105}$. Show that $7\mid A$.

My attempt-

I tried to convert $3^{105}$ like this: $3^{105}\equiv 3\cdot(3^2)^{52}\equiv 3\cdot 9^{52}\equiv 3\cdot2^{52} \pmod 7$. And for $4^{105}$ I tried the same way to convert it into $4\cdot 2^{52}$ but that's not possible and I'm getting $4^{79}\cdot 2^{52} \pmod 7$. I had the idea of doing it in $3^{105} + 4^{105}\equiv 3\cdot2^{52}+4\cdot 2^{52}\equiv 7\cdot2^{52}\equiv 0 \pmod 7$.

But I'm getting $4^{79}$ making it complex.

Can anyone suggest me some easier method? Please.

## marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jun 16 '17 at 19:37

• If $n$ is odd, $x^n + y^n$ has a factor of $x + y$. It's an identity. – quasi May 2 '17 at 5:19
• For example, you know how to factor $x^3+y^3$, right? How about $x^5 + y^5$? – quasi May 2 '17 at 5:21
• Isn't $4\equiv-3\pmod7$? – Lord Shark the Unknown May 2 '17 at 5:22
• Because you want to prove that $4^{105}\equiv-3^{105}\pmod7$. – Lord Shark the Unknown May 2 '17 at 5:33
• Taking quasi's hint one farther: $x^{105}+y^{105}=(x+y)(x^{104}-x^{103}\cdot y + \cdots - x \cdot y^{103}+y^{104})\,$. – dxiv May 4 '17 at 1:03

You can convert $4^{105}$ into $4\cdot2^{52}$ mod $7$, since $4^2=16\equiv2$ mod $7$:

$$4^{105}=4\cdot4^{2\cdot52}=4\cdot16^{52}\equiv4\cdot2^{52}$$

This gives you

$$3^{105}+4^{105}\equiv3\cdot2^{52}+4\cdot2^{52}=7\cdot2^{52}\equiv0\mod 7$$

The integer $A=3^{105}+4^{105}=3^{105}-(-4)^{105}$ is a multiple of $7=3-(-4)$, because $x-a$ is always a factor of the polynomial $x^{n}-a^{n}$, $n\in \mathbb{N}$.

By the binomial theorem, $4^{105}=(7-3)^{105}=7a-3^{105}$.

${\rm mod}\ 7\!:\,\ 4\equiv -3\ \Rightarrow\ \color{#c00}{4^{\large 105}}\equiv(-3)^{\large 105}\equiv\color{#0a0}{-3^{\large 105}}\$ by the Congruence Power Rule.

Therefore $\ A = 3^{\large 105} + \color{#c00}{4^{\large 105}}\equiv\, 3^{\large 105} \color{#0a0}{- 3^{\large 105}}\equiv\, 0\$ by the Congruence Sum Rule.