1. ## 5^n=3^n+8 (mod 26)

Solve for $\displaystyle n\in\mathbb{Z}$: $\displaystyle 5^n\equiv 3^n+8\mod 26$.

2. Originally Posted by james_bond
Solve for $\displaystyle n\in\mathbb{Z}$: $\displaystyle 5^n\equiv 3^n+8\mod 26$.

$\displaystyle \displaystyle{5^n=\left\{\begin{array}{rl}5\!\!\pm od {26}&\mbox{ , if }n=1\!\!\pmod 4\\-1\!\!\pmod{26}&\mbox{ , if }n=2\!\!\pmod 4\\-5\!\!\pmod{26}&\mbox{ , if }n=3\!\!\pmod 4\\1\!\!\pmod{26}&\mbox{ , if }n=0\!\!\pmod 4\end{array}\right.\,,\,\,3^n=\left\{\begin{array} {rl}3\!\!\pmod {26}&\mbox{ , if }n=1\!\!\pmod 3\\9\!\!\pmod{26}&\mbox{ , if }n=2\!\!\pmod 3\\1\!\!\pmod{26}&\mbox{ , if }n=0\!\!\pmod 3\end{array}\right.$

Now try to solve with the above hint...

Tonio

3. No solutions? Thx. But I don't really understand the first part but I get the idea. If n is even than $\displaystyle 5^n = \pm 1 (\mod 26)$, if n is odd than $\displaystyle 5^n = \pm 5 (\mod 26)$. But if we take a look at the other side of the congruence: $\displaystyle RHS=11\text{ or }17\text{ or }9 (\mod 26)$.

4. Originally Posted by tonio
$\displaystyle \displaystyle{5^n=\left\{\begin{array}{rl}-1\!\!\pmod {26}&\mbox{ , if }n=1\!\!\pmod 3\\-5\!\!\pmod{26}&\mbox{ , if }n=2\!\!\pmod 3\\1\!\!\pmod{26}&\mbox{ , if }n=0\!\!\pmod 3\end{array}\right.\,,\,\,3^=\left\{\begin{array}{ rl}3\!\!\pmod {26}&\mbox{ , if }n=1\!\!\pmod 3\\9\!\!\pmod{26}&\mbox{ , if }n=2\!\!\pmod 3\\1\!\!\pmod{26}&\mbox{ , if }n=0\!\!\pmod 3\end{array}\right.$

Now try to solve with the above hint...

Tonio
$\displaystyle 5^0 \equiv 1~\text{mod(26)}$, but $\displaystyle 5^3 \equiv 21~\text{mod(26)}$ and $\displaystyle 5^6 \equiv 25~\text{mod(26)}$...

-Dan

5. Originally Posted by topsquark
$\displaystyle 5^0 \equiv 1~\text{mod(26)}$, but $\displaystyle 5^3 \equiv 21~\text{mod(26)}$ and $\displaystyle 5^6 \equiv 25~\text{mod(26)}$...

-Dan
Yes, $\displaystyle 5^3\equiv 21\equiv -5$ (mod 26), and $\displaystyle 5^6\equiv 25\equiv -1$ (mod 26), just as tonio said.

6. Originally Posted by HallsofIvy
Yes, $\displaystyle 5^3\equiv 21\equiv -5$ (mod 26), and $\displaystyle 5^6\equiv 25\equiv -1$ (mod 26), just as tonio said.
But, for example, n = 0 implies n = 3k implies $\displaystyle 5^{3k} \equiv 1~\text{mod 26}$ according to tonio. If tonio is right, what am I missing?

-Dan

7. i feel i am missing something, too. 5 has order 4 in U(Z26), so i don't see how listing the values for n (mod 3) can possibly be right, whereas 3 has order 3. furthermore, 5^n (mod 26) never takes on any of the values 9,11 or 17 (mod 26). i don't see ANY solutions. and i don't agree with tonio's values of 5^n at ALL.

8. I can show that n, if it exists, must be an even number...Briefly, consider
$\displaystyle 5^n - 3^n \equiv 8$

$\displaystyle (5 - 3)(5^{n-1} + 5^{n-2} \cdot 3^1 +~...~+ 5^1 \cdot 3^{n - 2} + 3^{n - 1} ) = 8$

Divide both sides by 2 and we see that the remaining factor on the LHS must have an even number of terms. Thus n - 1 is odd and n is even.

I can't seem to make it beyond this point.

-Dan

Edit: I might be able to finish this (proving there are no solutions), but I'm not certain on the logic. I'll throw it out.

If n is even let it be n = 2a. Then
$\displaystyle 5^{2a} - 3^{2a} \equiv 8$

$\displaystyle 5^{2a} - 3^{2a} \equiv (5 + 3)(5 - 3)(......) \equiv 8$

$\displaystyle 5^{2a} - 3^{2a} \equiv (8)(2)(......) \equiv 8$

$\displaystyle 2(......) \equiv 1$

But in $\displaystyle (\mathbb{Z}_{26},~*)$ there are no even factors of 1. Thus a doesn't exist, and nor does n.

9. Originally Posted by topsquark
I can show that n, if it exists, must be an even number...Briefly, consider
$\displaystyle 5^n - 3^n \equiv 8$

$\displaystyle (5 - 3)(5^{n-1} + 5^{n-2} \cdot 3^1 +~...~+ 5^1 \cdot 3^{n - 2} + 3^{n - 1} ) = 8$

Divide both sides by 2 and we see that the remaining factor on the LHS must have an even number of terms. Thus n - 1 is odd and n is even.

I can't seem to make it beyond this point.

-Dan

Edit: I might be able to finish this (proving there are no solutions), but I'm not certain on the logic. I'll throw it out.

If n is even let it be n = 2a. Then
$\displaystyle 5^{2a} - 3^{2a} \equiv 8$

$\displaystyle 5^{2a} - 3^{2a} \equiv (5 + 3)(5 - 3)(......) \equiv 8$

$\displaystyle 5^{2a} - 3^{2a} \equiv (8)(2)(......) \equiv 8$

$\displaystyle 5^{2a} - 3^{2a} \equiv 2(......) \equiv 1$

But in $\displaystyle (\mathbb{Z}_{26},~*)$ there are no even factors of 1. Thus a doesn't exist, and nor does n.

I made a mistake in the table for $\displaystyle 5^n$ which I corrected after editing.

Tonio

10. Originally Posted by topsquark
I can show that n, if it exists, must be an even number...Briefly, consider
$\displaystyle 5^n - 3^n \equiv 8$

$\displaystyle (5 - 3)(5^{n-1} + 5^{n-2} \cdot 3^1 +~...~+ 5^1 \cdot 3^{n - 2} + 3^{n - 1} ) = 8$

Divide both sides by 2 and we see that the remaining factor on the LHS must have an even number of terms. Thus n - 1 is odd and n is even.
divide by 2? 2 is a zero-divisor in Z26, i don't think that's a good idea.....

5^n = 5 ≠ 11 = 3^n + 8 if n ≡ 1 (mod 12)
5^n = 25 ≠ 17 = 3^n + 8 if n ≡ 2 (mod 12)
5^n = 21 ≠9 = 3^n + 8 if n ≡ 3 (mod 12)
5^n = 1 ≠ 11 = 3^n + 8 if n ≡ 4 (mod 12)
5^n = 5 ≠ 17 = 3^n + 8 if n ≡ 5 (mod 12)
5^n = 25 ≠ 9 = 3^n + 8 if n ≡ 6 (mod 12)
5^n = 21 ≠11 = 3^n + 8 if n ≡ 7 (mod 12)
5^n = 1 ≠ 17 = 3^n + 8 if n ≡ 8 (mod 12)
5^n = 5 ≠ 9 = 3^n + 8 if n ≡ 9 (mod 12)
5^n = 25 ≠ 11 = 3^n + 8 if n ≡ 10 (mod 12)
5^n = 21 ≠17 = 3^n + 8 if n ≡ 11 (mod 12)
5^n = 1 ≠ 9 = 3^n + 8 if n ≡ 0 (mod 12)

no solution.....

11. Originally Posted by Deveno
divide by 2? 2 is a zero-divisor in Z26, i don't think that's a good idea.....
Heh. I uh, just put that there to see if you were looking carefully. Yeah, that's it.

-Dan