# exercise in Number Theory

• May 22nd 2008, 12:07 AM
closebelow
exercise in Number Theory
This exercise has also been posted yesterday at the cryptography help thread. Since my deadline for delivery has approached earlier I decided to move it here. I don't believe it is related to cryptography as much as Number's Theory.

Prove that the following is true:

11^n + 5^n = 0 (mod7) when n = 3 (mod6)
Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)

• May 22nd 2008, 12:18 AM
Moo
Hello,

Quote:

Originally Posted by closebelow
Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)

Are you sure that $11^3=1 \mod 3$ ?

Because it would mean that $11^3-1$ is a multiple of 3.
But $11^3=1331$ and $1331-1=1330$, which is obviously not a multiple of 3 (Worried)
• May 22nd 2008, 12:24 AM
Isomorphism
Quote:

Originally Posted by closebelow
This exercise has also been posted yesterday at the cryptography help thread. Since my deadline for delivery has approached earlier I decided to move it here. I don't believe it is related to cryptography as much as Number's Theory.

Prove that the following is true:

11^n + 5^n = 0 (mod7) when n = 3 (mod6)
Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)

Ya moo, he is wrong. It should actually read:
11^3 = 1 (mod7) and 5^3 = -1 (mod7)

n = 3 (mod6) means 6|(n-3). But this means 3|n. Thus n = 3k where k is an integer.
So 6|3(k-1) and thus 2|k-1 and therefore k is odd.

Now since k is odd,

11^n + 5^n = 11^3k + 5^3k = 1 + (-1)^k = 1 + -1 = 0 (mod7)

Aliter:Induction:
For n=1, follows from hint.
Assume for n and prove for n+6

Read the below line modulo 7,

11^(n+6) + 5^(n+6) = 11^n 11^6 + 5^n 5^6 = 11^n (11^3)^2 + 5^n (5^3)^2 = 11^n (1)^2 + 5^n (-1)^2 = 11^n + 5^n

But 11^n + 5^n mod 7 = 0, by induction hypothesis :)
• May 22nd 2008, 12:28 AM
Moo
Ah, I was wondering why he was given mod 3's.

Here's another approach :

$n=3 \mod 6$

This means that $n=3+6k \ , k \in \mathbb{Z}$

$\implies 11^n+5^n=11^3 \cdot (11^6)^k+5^3 \cdot (5^6)^k$, by using the power rules ! **

From Fermat's little theorem, we know that $11^6=1 \mod 7$ and $5^6=1 \mod 7$

Therefore :

$11^n+5^n=11^3 \cdot (11^6)^k+5^3 \cdot (5^6)^k=11^3 \cdot 1^k+5^3 \cdot 1^k \mod 7$

$11^n+5^n=11^3+5^3 \mod 7$

$11^n+5^n=1-1 \mod 7$

QED.

--------------

** as a recall :

$a^{b+c}=a^b \cdot a^c$

$a^{mn}=(a^m)^n=(a^n)^m$
• May 22nd 2008, 12:44 AM
closebelow
Hello guys and thanks for your help

I'm sorry but the exercise as given is like this:

Prove that the following is true: 11^n + 5^n = 0 (mod7) when n = 3 (mod6)
Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)