Divisible by 13 or not

SOLUTION ONE

Lemma : $x^n+y^n$ is divisible by $x+y$ when $n$ is odd.

Proof: Substitute $x=-y$ . (note that $(-y)^n=-y^n$ because $n$ is odd): $(-y)^n+y^n=-y^n+y^n=0$

Therefore, by the multivariable factor theorem , $x+y$ is a factor of $x^n+y^n$ .

The result follows by substituting $x=7$ , $y=6$ , $n=103$ .

---

SOLUTION TWO

Let $7^d+6^d$ be divisible by 13. Let $7^d+6^d=13m$ .

Then:

• $7^{d+2}+6^{d+2}$
• $=49\times7^d+36\times6^d$
• $=13\times7^d+36\times7^d+36\times6^d$
• $=13\times7^d+36(7^d+6^d)$
• $=13\times7^d+36\times13m$
• $=13(7^d+36m)$
• is also divisible by $13$ .

Note that $d=1$ makes $7^d+6^d=7+6=13$ divisible by $13$ .

Therefore, $d=1+2n$ also makes $7^d+6^d$ divisible by $13$ .

The result follows from substituting $n=51\implies d=103$ .

(This solution is similar to the Mathematical Induction )

$7 = -6 mod \ 13$

$6 = 6 mod \ 13$

Therefore: $7^{103} + 6^{103} \ mod 13 = (-6)^{103} + 6^{103} \ mod \ 13 = 0 \ mod \ 13$

Suppose 13|7^(103)+6^(103)

We know 7 is congruent with -6 mod13, therefore 7^(103) is congruent with -6^(103) mod13. We substitute 7^(103) by its congruency mod13 and we get:

13|(-6)^(103)+6^(103)

Because -6 has an odd exponent, (-6)^(103) is also negative, making (-6)^(103)+6^(103) equals zero, therefore:

13|0

As we wanted to prove.

A/C 7^103 + 6^103 Taking common 103, (7+6)^103 = 13^103

As the base is 13, hence it is clear that what ever the result will be, it would get definitely divided by 13.