mersenneforum.org > Math 2/3 Powers being viewed over the Ring Z/(10^n)Z
 Register FAQ Search Today's Posts Mark Forums Read

 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
2012-02-20, 02:42   #3
CRGreathouse

Aug 2006

2·2,963 Posts

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.

2012-02-20, 02:47   #4
CRGreathouse

Aug 2006

2×2,963 Posts

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.

2012-02-20, 07:30   #5
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

125710 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 1 2018-01-05 09:30 paul0 Computer Science & Computational Number Theory 4 2015-01-09 14:57 Flatlander Lounge 19 2013-09-24 05:27 JohnFullspeed Programming 7 2011-05-27 07:09 nibble4bits Math 31 2007-12-11 12:56

All times are UTC. The time now is 09:34.

Tue Oct 20 09:34:13 UTC 2020 up 40 days, 6:45, 0 users, load averages: 1.66, 1.40, 1.45