Question

Euler's Theorem

How do you use Euler's theorem to show that
(x^12)+(y^12) is congruent to 0,1,2 mod13 ?

Answer 1

Are these three seperate problems?

\[x^{12} + y^{12} \equiv 0 \pmod{13}\]
\[x^{12} + y^{12} \equiv 1 \pmod{13}\]
\[x^{12} + y^{12} \equiv 2 \pmod{13}\]

Answer 2

When you say Euler's Theorem, are you using Euler's generalization of Fermat's Little Theorem that if (a,m) = 1 then \(a^\phi(m) \equiv 1 \pmod{m}\)

Answer 3

The full example is as follows:

"Example 6.
The Diophantine equation \[x ^{12}+ y ^{12} = z ^{12} + w ^{12} + 3\] has no solutions

We show that the congruence \[x ^{12}+ y ^{12} = z ^{12} + w ^{12} + 3(mod13)\] has no solutions, using Euler's Theorem."

Answer 4

to get the \(\pmod{13}\) use the code \pmod{13}

Answer 5

By \(\phi(m)\) I mean Euler's function that counts the number of positive integers less than \(m\) that are relativly prime to \(m\).

Answer 6

So you might note that \(\phi(m) = 12\).

Answer 7

So, I'm not sure if this is the right path, but we can start with a few basics. First off, note that for \(a, b,c, d \in \mathbb{Z}\) if \(a \equiv b \pmod{m}\) and \(c \equiv d \pmod{m}\) then \(a + c\equiv b + d \pmod{m}\).

We can relate this to the example by replacing \(x^{12}\) with \(a\) and so on.

Answer 8

Ok maybe that last line is not exactly correct...

Answer 9

That's where Euler's Theorem may come in. Since \(\phi(13) = 12\) then any integer les that 13 should solve the congruence \(a^{12} \equiv 1 \pmod{13}\). Shall we check it?

Answer 10

Okay I'm with you so far

Answer 11

\(1^{12} = 1 \equiv 1 \pmod{13}\)
\(2^{12} = 4096 \equiv 1 \pmod{13}\)
\(3^{12} = 531441 \equiv 1 \pmod{13}\)

so far so good...

Answer 12

Yep :)

Answer 13

Ok so suppose x and y are two positive integers less that 13, then
\(x^{12} \equiv 1 \pmod{13}\) and \(y^{12} \equiv 1 \pmod{13}\) so \(x^{12} + y^{12} \equiv 1 + 1 = 2 \pmod{13}\)

Answer 14

But what about integers larger that 13, or nonpositive integers?

Answer 15

For instance what about \(14^{12}\)?

Answer 16

Note that we usually use the reduced residue system when working with congruences, for examle, \(14 \equiv 1 \pmod{13}\) and so is \(14\cdot 14 \equiv 1 \cdot 1 \pmod{13}\).
Thus \(14^{12} \equiv 1 \pmod{13}\)

Answer 17

And \(15 \equiv 2 \pmod{13}\) so by repeated multiplications \(15^{12} \equiv 2^{12} \equiv 1 \pmod{13}\)\)

Answer 18

right okay, I understand

Answer 19

So any integer can be matched with another integer for the set of positive integers less that 13. So we get that \(x^{12} \equiv y^{12} \equiv z^{12} \equiv w^{12} \equiv 1 \pmod{13}\)

Answer 20

So on the left hand side of the example you get 2 and on the right hand side you get 5 and \(2 \not\equiv 5 \pmod{13}\)

Answer 21

So maybe that's what they mean by using Euler's theorem.

Answer 22

Oh I get it!
Thankyou so much! That was a really good way of explaining it [and simplifying it!]

I'll do a few more practice questions!

Answer 23

Ohhh... wait, x,y,z,w have to be relativly prime to 13!!

Answer 24

I said above "any integer". It doesn't change things for this example because and power of any multiply of 13 will be congruent to 0 mod 13. Just something to keep in mind :)

Answer 25

So to be exact:
On the left hand side you could have 0, 1, or 2 (like your original post)
On the right hand side you could get 3, 4, or 5
So still no solution to example 6.

Answer 26

Right okay, I followed that completely [I think anyway, i'll soon find out when I do another example!]

Again, thankyou!

Answer 27

Thank you! Fun question.