5
$\begingroup$

If $\gcd(m,15)=\gcd(n,15)=1$ show $15\mid (m^4+n^4)$ or $15\mid (m^4-n^4)$.

This is what I have so far but I'm stuck on essentially the last step.

Proof: Assume $\gcd(m,15)=\gcd(n,15)=1$. By the Euler's Phi Function: If $\gcd(a,m)=1$ then $a^{\phi (m)}\equiv 1 \pmod m$.

$\phi(15)=\phi(5)\phi(3)=(5-1)(3-1)=8$

Hence, $m^8\equiv 1 \pmod{15}$ and $n^8\equiv 1 \pmod{15}$.

Then, $m^8\equiv 1 \pmod{15}\iff 15\mid m^8-1$. Similarly $15\mid n^8-1$.

Divisibility property sates if $a\mid b$ and $a\mid c$ then $a\mid b\pm c$.

So $15\mid (m^8-1)-(n^8-1) \Rightarrow 15\mid m^8-n^8$

So I believe I'm right up to this point, please correct if I'm not. I know that $m^8-n^8$ factors to $(m^4+n^4)(m^4-n^4)$ however since $15$ is not a prime number I can't assume $15\mid m^4+n^4$ or $15\mid m^4-n^4$.

Please help on these last few steps. Thanks.

$\endgroup$
2
$\begingroup$

Since none of the existing answers is built-up on OP's work, I posted another one.

OP has proved $15\mid m^8-n^8 = (m^4-n^4)(m^4+n^4)$.

Since $15$ is a composite number, to apply Euclid's Lemma, we have to do so in two steps (on prime number $3$ and $5$).

Note that (without Fermat's Little Theorem)

  • $a^2 \equiv 0, 1 \pmod 3$, so $a^4 \equiv 0,1 \pmod 3$.
    • If $3 \mid m^4 + n^4$, it's easy to see that the only possibility is that $3 \mid m,n$, which contradicts $\gcd(m,15) = \gcd(n,15) = 1$
    • Use Euclid's Lemma to show that $3 \mid m^4 - n^4$
  • $a^2 \equiv 0, 1, 4 \pmod 5$, so $a^4 \equiv 0,1 \pmod 5$, and $m^4 + n^4 \equiv 0,1,2 \pmod 5$.
    • If $5 \mid m^4 + n^4$, its again easy to see that the only possibility is $5 \mid m,n$, which contradicts $\gcd(m,15) = \gcd(n,15) = 1$
    • Use Euclid's Lemma to show that $5 \mid m^4 - n^4$

Since $\gcd(3,5) = 1$, $15 \mid m^4 - n^4$.

$\endgroup$
3
$\begingroup$

Since $\gcd(m,5) = \gcd(n,5)=1$ we have by Fermat little theorem:

$$ m^4\equiv 1\equiv n^4 \pmod 5$$ so $5\mid m^4-n^4$.

On the other hand since $\gcd(m,3) = \gcd(n,3)=1$ we have again by Fermat little theorem:

$$ m^2\equiv 1\equiv n^2 \pmod 3$$ so $3\mid m^2-n^2$ and so $3\mid m^4-n^4$

$\endgroup$
  • 1
    $\begingroup$ So you're saying that because it's divisible by 3 and 5 then it must be divisible by 15 right? $\endgroup$ – Luis Robles Mar 24 '18 at 20:29
  • 1
    $\begingroup$ Yes............. $\endgroup$ – Aqua Mar 24 '18 at 20:30
1
$\begingroup$

This question looks familiar... At any rate, the conclusion $15 \mid (m^4 + n^4)$ is unnecessary. As noted before, applying Fermat's Little Theorem with the primes 3 and 5 is all you need to solve this question.

$\endgroup$
0
$\begingroup$

Good work! Have you checked the $4$th powers $\mod 15$? For what numbers (with $\gcd(k,15)=1$) can we say $k^4\equiv 1\mod 15$? Can you use that to finish your proof?

$\endgroup$
  • 1
    $\begingroup$ No I didn't check 4th powers and that makes sense. Thank you for the advice. $\endgroup$ – Luis Robles Mar 24 '18 at 20:40
0
$\begingroup$

If $m$ is co-prime to $15$ then $m$ is congruent modulo $15$ to a member of $\{\pm 1, \pm 2, \pm 4,\pm 8\}$ so for some $j\in \{0,1,2,3\}$ we have $$m^4\equiv (\pm 2^j)^4\equiv (2^4)^j\equiv 1^j \equiv 1 \mod 15 .$$

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