1
$\begingroup$

I'm trying to prove what he title says. I've found that (i'll type it that way for the sake of using less code i.e using $\vert$ instead of the congruence symbol) $13 \vert 3^3 -1$ and that $13 \vert 4^3 +1$. I know by the congruence properties that $13 \vert 4^3 + 3^3$ However I don't know how to follow from there, I multiplied by $3^{102}$$4^{102}$ and got that $13 \vert 3^{102} 4^{105}+ 3^{105}4^{102}$ but I don't think this will help me with something. Any help will be appreciated.

$\endgroup$
2
  • $\begingroup$ $3^{105} \equiv (3^3)^{35} \equiv 1^{35} \pmod {13}$. This is a consequence of how if $a \equiv b \pmod q$ then $a + x \equiv b + x \pmod q$ and $a x \equiv b x \pmod q$. $\endgroup$ – DanielV Oct 17 '17 at 3:14
  • 1
    $\begingroup$ Do you know Fermat's little theorem? $\endgroup$ – edm Oct 17 '17 at 3:14
3
$\begingroup$

$3^{105} = (3^{3})^{35} = (27)^{35} \equiv (1)^{35}(\bmod\; 13) = 1$

$4^{105} = (4^{3})^{35} = (64)^{35} \equiv (-1)^{35}(\bmod\; 13) = -1$

Adding both we have

$1+(-1)=0$

QED.

$\endgroup$
3
  • 1
    $\begingroup$ Hmm I don't really see where FLT was used, I just see that $3^3 \equiv 1 \pmod {13}$ was used. $\endgroup$ – Ovi Oct 17 '17 at 3:33
  • $\begingroup$ Is $a^k \equiv b^k \;(\bmod\; n)$ derived from Fermat's little theorem? $\endgroup$ – andrespm Oct 17 '17 at 3:36
  • $\begingroup$ @Ovi Thanks. FLT was not used. Error on my part. $\endgroup$ – Sagar Chand Oct 17 '17 at 4:23
1
$\begingroup$

$$3^{105} + 4^{105} = (3^3)^{35} + (4^5)^{21} = 27^{35} + 1024^{21} \equiv 1^{35} + (-3)^{21} = 1 + (-1)(3^3)^7 \\ \equiv -1 + 1 = 0 \pmod {13}$$

$\endgroup$
1
$\begingroup$

Following your way, it is sufficient to establish $$(3^3)^{35}+(4^3)^{35}$$ is divisible by $3^3+4^3$ which is evident from Proof of $a^n+b^n$ divisible by a+b when n is odd

$\endgroup$
0
$\begingroup$

You can also say that if $n$ is a natural number and divisible by 3, say $n=3k$ with $k$ odd, then:

$$3^{n}+4^{n}=3^{3k}+4^{3k}=(3^{3})^{k}+(4^{3})^{k}=27^k+64^k\equiv 1^k+(-1)^k=0\,(\ {\rm mod}\ 13)$$

because: $\ 27\equiv 1 ({\rm mod}\ 13)$ and $\ 64\equiv -1 ({\rm mod}\ 13)$

$\endgroup$
2
  • $\begingroup$ This little generalization was suggested in a discussion with my collegue José Eduardo Blazek. $\endgroup$ – Hector Blandin Oct 18 '17 at 17:03
  • $\begingroup$ Obviously, this was already showed by previous answer using $a+b$ divides $a^n+b^n$ when $n$ is odd . $\endgroup$ – Hector Blandin Oct 18 '17 at 17:05

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.