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?

Printable View

- Feb 17th 2009, 08:19 AMmathisthebestpuzzlex 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? - Feb 17th 2009, 08:42 AMoswaldo
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. - Feb 17th 2009, 09:56 AMMoo
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,

Here, n=10. So

Hence for any x,

This means that they have the same last digit - Feb 17th 2009, 02:17 PMJaneBennet
No, no. It’s provided

Hence when

You still have to check the cases by other methods. - Feb 17th 2009, 02:45 PMJaneBennet
Okay, for 1, 3, 7, 9, you apply as above.

For the even digits, try

So for

(multiply through by 2)

Hence for

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. - Feb 17th 2009, 02:47 PMmathisthebestpuzzle
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). - Feb 17th 2009, 05:46 PMPaulRS
Read the thread here (it's pretty much the same)

Here there's an interesting way to see that is a primitive root module (Happy)

First note that , so, more generally consider the primes of the form with prime

Now, we have: primitive roots module

And non-quadratics residues module q. (if is a primitive root module q they are of the form 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 it follows that is soluble and has 2 incongruent solutions. For which thus by Euler's criterion both solutions are non-quadratic residues.

But: 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 are primitive roots!

3 is a non-quadratic residue mod 29 since (the rest follows by Euler's Criterion). We may also do this by applying the Quadratic Reciprocity Theorem, indeed: hence and since it follows that and it's a non-quadratic residue

Now in our case it remains to check that which indeed holds ! (Happy) - Feb 17th 2009, 08:05 PMmathisthebestpuzzle
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! - Feb 17th 2009, 08:24 PMmathisthebestpuzzle
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 - Feb 18th 2009, 05:13 AMPaulRS
Since 3 is a primitive root, for some k (if such a solution exists), hence and this happens if and only if 28 divides 5k+1, again because 3 is a primitive root module 29.

Okay, we have (1) for some . Read this equation mod 5, we have if and only if thus, dividing through by 3 which is coprime to the module: thus

Substitute this back into (1) to get thus divide by 5: thus (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 (3)

Okay, it should be easy to note that now multiply by (by (3) ) hence

Now, since 3 is a primitive root, it follows that if and only if

So if and only if

We can now also simplify (2) fastly using property (3), we have

Again which is evidently since

Thus we get