mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   2/3 Powers being viewed over the Ring Z/(10^n)Z (https://www.mersenneforum.org/showthread.php?t=16546)

 Raman 2012-02-19 17:02

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

1 Attachment(s)
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 [TEX]\phi(n)[/TEX],

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
[TEX]2^{20} = 76 (mod 100)[/TEX] => is being the identity element over Z/100Z
[TEX]2^{100} = 376 (mod 1000)[/TEX] => is being the identity element over Z/1000Z
[TEX]2^{500} = 9376 (mod 10000)[/TEX]
[TEX]2^{2500} = 9376 (mod 100000)[/TEX]
[TEX]2^{12500} = 109376 (mod 1000000)[/TEX]
[TEX]2^{62500} = 7109376 (mod 10000000)[/TEX]
...

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

[ATTACH]7675[/ATTACH]

 Raman 2012-02-19 17:04

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

Unlike this, for the powers of 3, although over the ring Z/100Z
all the 20 elements [TEX]\equiv[/TEX] 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?

[ATTACH]7676[/ATTACH]

 CRGreathouse 2012-02-20 02:42

[QUOTE=Raman;289986][TEX]2^{20} = 76 (mod 100)[/TEX] => is being the identity element over Z/100Z[/QUOTE]

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=Raman;289986][TEX]3^{2500} \ne 1 (mod 100000)[/TEX] => is Not being the identity element at all[/QUOTE]

No, the identity is 3^5000 = 1.

 CRGreathouse 2012-02-20 02:47

[QUOTE=Raman;289987]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?[/QUOTE]

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=CRGreathouse;290035]
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]

What I meant was that 76 is being the multiplicative identity element from among the 20 generated elements inside Z/100Z [TEX]\equiv[/TEX] {4 (mod 100)} - {20 (mod 100)}

[QUOTE=CRGreathouse;290035]
No, the identity is 3^5000 = 1.
[/QUOTE]
While the group order for the element 2 (mod 10[sup]n[/sup]) is being
given correctly to be [/B][B]10[sup]n[/sup]/5*2[sup]n-2[/sup],
why not such a thing as this not hold out at all for the element 3 as well, as since?[/B]

[QUOTE=CRGreathouse;290036]
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.
[/QUOTE]
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[sup]n[/sup]) for the values for n > 4 at all.

[SIZE=1]The discrete logarithm from inside for the ring Z/(10[sup]n[/sup])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[sup]m[/sup] = x (mod 10[sup]n[/sup])
=> 2[sup]?[/sup] = x+10[sup]n[/sup]k (mod 10[sup]n+1[/sup]), 0 [TEX]\le[/TEX] k [TEX]\le[/TEX] 9
? = m + r (10[sup]n[/sup]/5*2[sup]n-2[/sup]), 0 [TEX]\le[/TEX] r [TEX]\le[/TEX] 4

this is being the values for itself
this technique does not hold out, applicable for the prime order field in general at all.[/SIZE]

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