x and x^5 have the same final digit

**mathisthebestpuzzle** · February 17th 2009, 07:19 AM

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?

**oswaldo** · February 17th 2009, 07:42 AM

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.

**Moo** · February 17th 2009, 08:56 AM

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

**JaneBennet** · February 17th 2009, 01:17 PM

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.

**JaneBennet** · February 17th 2009, 01:45 PM

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.

**mathisthebestpuzzle** · February 17th 2009, 01:47 PM

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).

**PaulRS** · February 17th 2009, 04:46 PM

Originally Posted by mathisthebestpuzzle

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 $ 29 = 4 \cdot 7 + 1 $ , so, more generally consider the primes $q$ of the form $ q = 4 \cdot p + 1 $ with $p>2$ prime

Now, we have: $ \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}} {2} - 2 $ primitive roots module $q$

And $ \tfrac{{q - 1}} {2} $ non-quadratics residues module q. (if $ g $ 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 $ q\equiv{1}(\bmod.4) $ it follows that $ x^2 \equiv - 1\left( {\bmod .q} \right) $ is soluble and has 2 incongruent solutions. For which $ x^2 \equiv - 1\left( {\bmod .q} \right) \Rightarrow x^{\tfrac{{q - 1}} {2}} = \left( {x^2 } \right)^{\left( {\tfrac{{q - 1}} {4}} \right)} \equiv \left( { - 1} \right)^{\left( {\tfrac{{q - 1}} {4}} \right)} = - 1\left( {\bmod .q} \right) $ thus by Euler's criterion both solutions are non-quadratic residues.

But: $ x^2 \equiv - 1\left( {\bmod .q} \right) \Rightarrow x^2 \cdot x^{\tfrac{{q - 1}} {2}} \equiv \left( { - 1} \right) \cdot \left( { - 1} \right) = 1\left( {\bmod .q} \right) $ $ \Rightarrow x^{\tfrac{{q + 1}} {2}} \equiv \left( { - 1} \right) \cdot \left( { - 1} \right) = 1\left( {\bmod .q} \right) $ 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 $ x^2 \equiv - 1\left( {\bmod .q} \right) $ 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 $ 3^2 \not\equiv - 1\left( {\bmod .29} \right) $ which indeed holds !

**mathisthebestpuzzle** · February 17th 2009, 07:05 PM

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!

**mathisthebestpuzzle** · February 17th 2009, 07:24 PM

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

**PaulRS** · February 18th 2009, 04:13 AM

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)$

Thread: x and x^5 have the same final digit

LinkBack

Thread Tools

Display

x and x^5 have the same final digit

Similar Math Help Forum Discussions

The last digit of 7^7^7

Digit sum & digit product of number x

digit nos

Final Digit of 3^1001

decimal digit as final digit

Search Tags