Results 1 to 11 of 11

Math Help - 5^n=3^n+8 (mod 26)

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    5^n=3^n+8 (mod 26)

    Solve for n\in\mathbb{Z}: 5^n\equiv 3^n+8\mod 26.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by james_bond View Post
    Solve for n\in\mathbb{Z}: 5^n\equiv 3^n+8\mod 26.

    \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
    Last edited by tonio; April 3rd 2011 at 02:16 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2007
    Posts
    329
    No solutions? Thx. But I don't really understand the first part but I get the idea. If n is even than 5^n = \pm 1 (\mod 26), if n is odd than 5^n = \pm 5 (\mod 26). But if we take a look at the other side of the congruence: RHS=11\text{ or }17\text{ or }9 (\mod 26).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,903
    Thanks
    329
    Awards
    1
    Quote Originally Posted by tonio View Post
    \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
    5^0 \equiv 1~\text{mod(26)}, but 5^3 \equiv 21~\text{mod(26)} and 5^6 \equiv 25~\text{mod(26)}...

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,596
    Thanks
    1421
    Quote Originally Posted by topsquark View Post
    5^0 \equiv 1~\text{mod(26)}, but 5^3 \equiv 21~\text{mod(26)} and 5^6 \equiv 25~\text{mod(26)}...

    -Dan
    Yes, 5^3\equiv 21\equiv -5 (mod 26), and 5^6\equiv 25\equiv -1 (mod 26), just as tonio said.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,903
    Thanks
    329
    Awards
    1
    Quote Originally Posted by HallsofIvy View Post
    Yes, 5^3\equiv 21\equiv -5 (mod 26), and 5^6\equiv 25\equiv -1 (mod 26), just as tonio said.
    But, for example, n = 0 implies n = 3k implies 5^{3k} \equiv 1~\text{mod 26} according to tonio. If tonio is right, what am I missing?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,385
    Thanks
    751
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,903
    Thanks
    329
    Awards
    1
    I can show that n, if it exists, must be an even number...Briefly, consider
    5^n - 3^n \equiv 8

    (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
    5^{2a} - 3^{2a} \equiv 8

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

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

    2(......) \equiv 1

    But in  (\mathbb{Z}_{26},~*) there are no even factors of 1. Thus a doesn't exist, and nor does n.
    Last edited by topsquark; April 3rd 2011 at 03:19 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by topsquark View Post
    I can show that n, if it exists, must be an even number...Briefly, consider
    5^n - 3^n \equiv 8

    (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
    5^{2a} - 3^{2a} \equiv 8

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

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

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

    But in  (\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 5^n which I corrected after editing.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,385
    Thanks
    751
    Quote Originally Posted by topsquark View Post
    I can show that n, if it exists, must be an even number...Briefly, consider
    5^n - 3^n \equiv 8

    (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.....
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,903
    Thanks
    329
    Awards
    1
    Quote Originally Posted by Deveno View Post
    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
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum