2/3 Powers being viewed over the Ring Z/(10^n)Z

Raman · 2012-02-19, 17:02

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: 231
Size: 24.8 KB
ID: 7675

Raman · 2012-02-19, 17:04

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: 221
Size: 20.3 KB
ID: 7676

CRGreathouse · 2012-02-20, 02:42

Quote:

Originally Posted by Raman

$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

$3^{2500} \ne 1 (mod 100000)$ => is Not being the identity element at all

No, the identity is 3^5000 = 1.

CRGreathouse · 2012-02-20, 02:47

Quote:

Originally Posted by Raman

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.

Raman · 2012-02-20, 07:30

I will rather certainly to be back within a while.

Quote:

Originally Posted by CRGreathouse

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

No, the identity is 3^5000 = 1.

The question was this, being stated as follows
While the group order for the element 2 (mod 10ⁿ) is being
given correctly to be 10ⁿ/5*2^n-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

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 10ⁿ) for the values for n > 4 at all.

The discrete logarithm from inside for the ring Z/(10ⁿ)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

2^m = x (mod 10ⁿ)
=> 2^? = x+10ⁿk (mod 10ⁿ⁺¹), 0 $\le$ k $\le$ 9
? = m + r (10ⁿ/5*2^n-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.

2012-02-19, 17:02	#1
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts	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)$

2012-02-19, 17:04	#2
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts	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? Last fiddled with by Raman on 2012-02-19 at 17:24

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