mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-02-19, 17:02   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default 2/3 Powers being viewed over the Ring Z/(10^n)Z

I am doing very severe load coursework for Ph.D. from IMSc, Chennai,
that's why I am not able tending to be active over this forum for the past year at all.

Very recently, I had come across some very fascinating property, for this,
I'd like (need) to seek the answer for this.

Euler's Theorem conveys necessarily that the order for an element over (mod n) is always being a divisor for \phi(n),

but though the properties for the powers of 2 & 3 vary accordingly as follows.
Why is it being so, the properties are rather being different from them apart?

As follows
2^{20} = 76 (mod 100) => is being the identity element over Z/100Z
2^{100} = 376 (mod 1000) => is being the identity element over Z/1000Z
2^{500} = 9376 (mod 10000)
2^{2500} = 9376 (mod 100000)
2^{12500} = 109376 (mod 1000000)
2^{62500} = 7109376 (mod 10000000)
...

Consider this, rather
3^{20} = 1 (mod 100)
3^{100} = 1 (mod 1000)
3^{500} = 1 (mod 10000)
3^{2500} \ne 1 (mod 100000) => is Not being the identity element at all
3^{12500} \ne 1 (mod 1000000) => WHY?
3^{62500} \ne 1 (mod 10000000)

Click image for larger version

Name:	2powers.gif
Views:	189
Size:	24.8 KB
ID:	7675
Raman is offline   Reply With Quote
Old 2012-02-19, 17:04   #2
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
Default

Next, for the powers of 2, over the ring Z/1000Z, all the 100 elements for the form \equiv 8 (mod 1000), \ne 40 (mod 1000) are being generated.

Unlike this, for the powers of 3, although over the ring Z/100Z
all the 20 elements \equiv 1, 3, 7, 9 (mod 20) are being generated, this does not hold out over on from the insider for the larger ring Z/1000Z at all.

For this example, the element 3, over on multiplication yields, generating the elements 1, 3, 9 (mod 1000), although the element 7 (mod 1000) is not being generated at all, although, instead it rather generates the element 507 (mod 1000), although, rather.

AGAIN WHY?
What is being it to be the true reason behind this, rather?
WHY?

Click image for larger version

Name:	3powers.gif
Views:	175
Size:	20.3 KB
ID:	7676

Last fiddled with by Raman on 2012-02-19 at 17:24
Raman is offline   Reply With Quote
Old 2012-02-20, 02:42   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

23×733 Posts
Default

Quote:
Originally Posted by Raman View Post
2^{20} = 76 (mod 100) => is being the identity element over Z/100Z
I'm not sure what you're saying here. 2^20 = 76 is not the identity element in Z/100Z. 2 divides 100, so no positive power of 2 can be the identity.

Quote:
Originally Posted by Raman View Post
3^{2500} \ne 1 (mod 100000) => is Not being the identity element at all
No, the identity is 3^5000 = 1.
CRGreathouse is offline   Reply With Quote
Old 2012-02-20, 02:47   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

23×733 Posts
Default

Quote:
Originally Posted by Raman View Post
For this example, the element 3, over on multiplication yields, generating the elements 1, 3, 9 (mod 1000), although the element 7 (mod 1000) is not being generated at all, although, instead it rather generates the element 507 (mod 1000), although, rather.

AGAIN WHY?
What is being it to be the true reason behind this, rather?
3 has order 100 in Z/1000Z, so it can't generate more than 100 of the 1000 elements. It misses 7, 11, 13, 17, 19, 21, ... as well as all multiples of 2 and 5.
CRGreathouse is offline   Reply With Quote
Old 2012-02-20, 07:30   #5
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

I will rather certainly to be back within a while.

Quote:
Originally Posted by CRGreathouse View Post
I'm not sure what you're saying here. 2^20 = 76 is not the identity element in Z/100Z. 2 divides 100, so no positive power of 2 can be the identity.
What I meant was that 76 is being the multiplicative identity element from among the 20 generated elements inside Z/100Z \equiv {4 (mod 100)} - {20 (mod 100)}

Quote:
Originally Posted by CRGreathouse View Post
No, the identity is 3^5000 = 1.
The question was this, being stated as follows
While the group order for the element 2 (mod 10n) is being
given correctly to be
10n/5*2n-2,
why not such a thing as this not hold out at all for the element 3 as well, as since?


Quote:
Originally Posted by CRGreathouse View Post
3 has order 100 in Z/1000Z, so it can't generate more than 100 of the 1000 elements. It rather misses out 7, 11, 13, 17, 19, 21, 23, 29, ... as well as all multiples of 2 and 5.
Why is it being so? Thus, why does it not generate at all, all the elements for the forms 1, 3, 7, 9, 21, 23, 27, 29, 41, 43, 47, 49, 61, 63, 67, 69, 81, 83, 87, 89 (mod 200) at all, even hereby?
For this example, such that
1, 3, 9, 27, 41, 43, 49, 67, 81, 83, 89
which are being generated
7, 21, 23, 29, 47, 61, 63, 69, 87
they are not being generated at all,
first of all, at once, for this

Or otherwise that is there a somewhat providable possible explicit formula given in order to determine which elements it can be able to generate, rather?

For this example, it does not violate the following rule at all, if it is being possible to generate x (mod 200), then it is not being possible to generate (x+100) mod 200 at all, although rather this does not hold out, applicable for the values for (mod 10n) for the values for n > 4 at all.

The discrete logarithm from inside for the ring Z/(10n)Z can be done within the polynomial time algorithm itself, as follows:
for the element 2, so for 3, as well as again, since it cycles every 20 elements, for last 2 digits, they can be checked out for the 20 elements by making use for the brute force techniques for the first place itself, and then
thus for the subsequent decimal places, within 5 values for the same decimal digit itself, as follows

2m = x (mod 10n)
=> 2? = x+10nk (mod 10n+1), 0 \le k \le 9
? = m + r (10n/5*2n-2), 0 \le r \le 4

this is being the values for itself
this technique does not hold out, applicable for the prime order field in general at all.
Raman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Ring of integers in an unknown field carpetpool Abstract Algebra & Algebraic Number Theory 1 2018-01-05 09:30
Ring Square Roots in NFS paul0 Computer Science & Computational Number Theory 4 2015-01-09 14:57
Identifying ring inscription Flatlander Lounge 19 2013-09-24 05:27
Ring Cardinal? JohnFullspeed Programming 7 2011-05-27 07:09
2^x using powers of e? nibble4bits Math 31 2007-12-11 12:56

All times are UTC. The time now is 12:16.

Mon Aug 10 12:16:02 UTC 2020 up 24 days, 8:02, 3 users, load averages: 2.05, 2.14, 1.95

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.