Results 1 to 10 of 10

Math Help - x and x^5 have the same final digit

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    47

    x and x^5 have the same final digit

    This seems as though it is a simple problem....but i'm stuck.

    Prove that x and x^5 have the same final digit for any integer x.

    is this done by induction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jan 2009
    Posts
    94
    This may not be the most ellequent proof but actually you enumerate this easily. Because there are only 10 possibilities for last digit. You can write last digit for x^2 then for x^4 and finally x^5. Last digits upto 4:

    x x^2 x^4 x^5
    0 0 0 0
    1 1 1 1
    2 4 6 2
    3 9 1 3
    4 6 6 4
    ...
    9 1 1 9

    -O

    Do not let the theory murder practice.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    The last digit represents the congruence modulo 10.

    If x=0 mod 10, then x^5=0 mod 10
    If x=1 mod 10, then x^5=1 mod 10
    If x=2 mod 10, then x^5=32 mod 10=2 mod 10
    and so on...


    Also, there is another way, if you've Studied Euler's theorem :
    For any x, x^{\varphi(n)} \equiv x (\bmod n)
    Here, n=10. So \varphi(n)=1 \cdot 4=4

    Hence for any x, x^4 \equiv x (\bmod 10)
    This means that they have the same last digit
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    No, no. It’s x^{\phi(n)}\equiv1\pmod n provided \gcd(x,n)=1.

    Hence x^5\equiv x\pmod{10} when x=1,3,7,9.

    You still have to check the cases x=2,4,5,6,8 by other methods.
    Last edited by JaneBennet; February 17th 2009 at 02:35 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Okay, for 1, 3, 7, 9, you apply \phi(10)=4 as above.

    For the even digits, try \phi(5)=4.

    So y^4\equiv1\pmod 5 for y=1,2,3,4.

    \therefore\ 2^4y^4\equiv16\pmod 5\equiv1\pmod 5

    \Rightarrow\ 2^5y^4\equiv2\pmod{10} (multiply through by 2)

    \Rightarrow\ (2y)^5\equiv2y\pmod{10}

    Hence x^5\equiv x\pmod{10} for x=2y=2,4,6,8.

    Finally, any power of any integer ending in 5 also ends in 5 and any power of any integer ending in 0 also ends in 0.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Apr 2008
    Posts
    47
    would you happen to know how to use discrete logarithms to find all solutions to the congruences 3x^5 = 1 (mod 29) and
    3^x = 2 (mod 29).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by mathisthebestpuzzle View Post
    would you happen to know how to use discrete logarithms to find all solutions to the congruences 3x^5 = 1 (mod 29) and
    3^x = 2 (mod 29).
    Read the thread here (it's pretty much the same)

    Here there's an interesting way to see that 3 is a primitive root module 29

    First note that <br />
29 = 4 \cdot 7 + 1<br />
, so, more generally consider the primes q of the form <br />
q = 4 \cdot p + 1<br />
with p>2 prime

    Now, we have: <br />
\phi \left( {q - 1} \right) = \phi \left( {4p} \right) = \phi \left( 4 \right) \cdot \phi \left( p \right) = 2 \cdot \left( {p - 1} \right) = \tfrac{{q - 1}}<br />
{2} - 2<br />
primitive roots module q

    And <br />
\tfrac{{q - 1}}<br />
{2}<br />
non-quadratics residues module q. (if <br />
g<br />
is a primitive root module q they are of the form g^{2s+1} and that is sufficient )

    Every primitive root is a non-quadratic residue (here), thus all quadratic residues save for 2 of them are primitive roots.

    Since <br />
q\equiv{1}(\bmod.4)<br />
it follows that <br />
x^2  \equiv  - 1\left( {\bmod .q} \right)<br />
is soluble and has 2 incongruent solutions. For which <br />
x^2  \equiv  - 1\left( {\bmod .q} \right) \Rightarrow x^{\tfrac{{q - 1}}<br />
{2}}  = \left( {x^2 } \right)^{\left( {\tfrac{{q - 1}}<br />
{4}} \right)}  \equiv \left( { - 1} \right)^{\left( {\tfrac{{q - 1}}<br />
{4}} \right)}  =  - 1\left( {\bmod .q} \right)<br />
thus by Euler's criterion both solutions are non-quadratic residues.

    But: <br />
x^2  \equiv  - 1\left( {\bmod .q} \right) \Rightarrow x^2  \cdot x^{\tfrac{{q - 1}}<br />
{2}}  \equiv \left( { - 1} \right) \cdot \left( { - 1} \right) = 1\left( {\bmod .q} \right)<br />
<br />
 \Rightarrow x^{\tfrac{{q + 1}}<br />
{2}}  \equiv \left( { - 1} \right) \cdot \left( { - 1} \right) = 1\left( {\bmod .q} \right)<br />
thus, the 2 incongruent solutions are non-quadratic residues and are not primitive roots!

    Hence all the non-quadratic residues mod. q save from the solutions to <br />
x^2  \equiv  - 1\left( {\bmod .q} \right)<br />
are primitive roots!

    3 is a non-quadratic residue mod 29 since 29|(3^{14}+1) (the rest follows by Euler's Criterion). We may also do this by applying the Quadratic Reciprocity Theorem, indeed: \left(\tfrac{3}{29}\right)_L\cdot\left(\tfrac{29}{  3}\right)_L=(-1)^{\tfrac{29-1}{2}\cdot \tfrac{3-1}{2}}=1 hence \left(\tfrac{3}{29}\right)_L=\left(\tfrac{29}{3}\r  ight)_L and since \left(\tfrac{29}{3}\right)_L\equiv{29^{\tfrac{3-1}{2}}}\equiv{-1}(\bmod.3) it follows that \left(\tfrac{3}{29}\right)_L=-1 and it's a non-quadratic residue

    Now in our case it remains to check that <br />
3^2  \not\equiv  - 1\left( {\bmod .29} \right)<br />
which indeed holds !
    Last edited by PaulRS; February 17th 2009 at 06:34 PM. Reason: Adding that p>2
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Apr 2008
    Posts
    47
    i need more explanation.

    so 3x^5 is congruent to 1 mod 29

    then x is congruent to 3^k mod 29

    3x^5 is congruent to 3^5k+1 is congruent to 1 mod 29

    3 is a primitive root iff 28|5k+1 ?

    PLEASE HELP!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Apr 2008
    Posts
    47
    ok, so i just checked the primitive roots of 29. until i found that

    15^5 is congruent to 10 mod 29.

    therefore x is congruent to 15 mod 29.

    How do i solve the second congruence?

    3^x is congruent to 2 mod 29.?!?!?1
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Since 3 is a primitive root,  x\equiv 3^k for some k (if such a solution exists), hence 3^{5k+1}\equiv 1 (\bmod.29) and this happens if and only if 28 divides 5k+1, again because 3 is a primitive root module 29.

    Okay, we have 28s=5k+1 (1) for some s\in \mathbb Z. Read this equation mod 5, we have 3s\equiv 1 (\bmod.5) if and only if 3s\equiv 1+5 =6(\bmod.5) thus, dividing through by 3 which is coprime to the module: s\equiv 2 (\bmod.5) thus s=5m+2

    Substitute this back into (1) to get 28\cdot 5\cdot m +56 = 5k+1 thus 28\cdot 5\cdot m +55 = 5k divide by 5: 28m+11=k thus x=3^{28m+11}=(3^{28})^m\cdot 3^{11}\equiv 3^{11} (\bmod. 29) (2)



    Now let's go to the second question.

    First I'll remark a property of the primitive roots which will fasten the calculations.

    Let g be a primitive root module n, then g^{\tfrac{\phi(n)}{2}}\equiv -1 (\bmod.n) (3)

    Okay, it should be easy to note that 3^3=27\equiv{-2}(\bmod.29) now multiply by 3^{14}\equiv{-1}(\bmod.29) (by (3) ) hence 3^{17}\equiv{2}(\bmod.29)

    Now, since 3 is a primitive root, it follows that 3^a\equiv 3^b (\bmod. 29) if and only if a\equiv b (\bmod. 28)

    So 3^x\equiv 2 (\bmod. 29) if and only if x\equiv 17 (\bmod.28)



    We can now also simplify (2) fastly using property (3), we have 3^{11}\equiv{3^{14}3^{-3}}\equiv (-1)\cdot (3^3)^{-1}(\bmod.29)

    Again (3^3)^{-1}\equiv (-2)^{-1}(\bmod.29) which is evidently -15 since (-2)\cdot (-15)=30=29+1

    Thus we get 3^{11}\equiv 15 (\bmod.29)
    Last edited by PaulRS; February 18th 2009 at 05:25 AM. Reason: typo changed 28 for 29
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The last digit of 7^7^7
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: November 5th 2011, 06:59 AM
  2. Digit sum & digit product of number x
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 19th 2011, 09:07 AM
  3. digit nos
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 28th 2009, 09:06 AM
  4. Final Digit of 3^1001
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 24th 2008, 12:47 PM
  5. decimal digit as final digit
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 25th 2008, 08:18 PM

Search Tags


/mathhelpforum @mathhelpforum