Register to reply

Generator of the additive gr. Z_m

by sutupidmath
Tags: additive, generator
Share this thread:
sutupidmath
#1
Nov20-08, 12:32 AM
P: 1,633
Hi all,

I am having trouble proving the following proposition:

[tex]\bar a[/tex] is a generator of the additive group [tex]Z_m [/tex] if and only if gcm(m,a)=1.

Well, first let's start with what i know.

I know how to prove the following:

Let G=[a] be a cyclic group of order q. Show that [tex] a^s[/tex] is a generator of G, iff gcd(s,q)=1.

proof:
(<=) Suppose that gcd(s,q)=1, then there exist some integers x,y such that

1=sx+qy, so

[tex]a^1=a^{sx}a^{qy}=(a^s)^x(a^q)^y=(a^s)^xe^y=(a^s)^x[/tex] so since there exists an integer x, such that [tex] (a^s)^x=a[/tex] then [tex] G=[a^s][/tex]

(=>) Now, suppose that [tex] a^s[/tex] is a generator of G. THen there should exist some integer k such that

[tex] (a^s)^k=a=>a^{sk}=a=>a^{sk-1}=e[/tex] now from a theorem we know that

q|(sk-1)=> there exists some integer n such that sk-1=mq=>1=sk+(-m)q=>gcd(s,q)=1.


Now i tried to translate this for the additive groups. And here is where the problems start to come in play, for only to get worse when i go to Z_m.

So, i am trying to prove the following:

Let G be an additive group generated by a, where o(G)=q. Prove that s*a is a generator of G iff gcd(s,q)=1.
Proof:
(<=) Suppose that gcd(s,q)=1. Now, as before, there exist x,y integers, such that

1=sx+qy

now: 1*a=(sx+qy)a=(sx)a+(qy)a= x(sa)+y(qa).---(@)
(Now, here i believe that if we Translate the Lagranges theorem into terms of an additive group it would be sth like this, right: "Let G be a finite group with order r. Then the order of each subgroup H in G, and the order of each element a of G is an integral divisor or r. Also r*g=0 for every el. g in G."Basically i am concerned whether the last part would be correct that is: from g^r =e into r*g=e=0. Since in the book we are using we are denoting with 0 the identity in an additive group.)

Now, if this is true, then we get from (@) a=x(sa). Now since there is an integer x, such that this holds, i assume we can conclude that G=[sa], that is sa generates the group G.

(=>) now lets suppose that sa is a generator for the group G. Then there exists some integer k such that k(sa)=a=> k(sa)-a=0 => (ks-1)a=0. Now, since the order of a is q. it follows that

q|(ks-1)=> ks-1=mq =>1=ks +(-m)q , so it follows that gcd(s,q)=1.

Well, let me give a crack to my main issue now:

[tex]\bar a[/tex] is a generator of the additive group [tex]Z_m [/tex] if and only if gcm(m,a)=1.
Proof: again lets suppose that gcd(a,m)=1. so there are integers x, y such that

1=ax+my.

Now, i know that [tex]\bar a = a+[m][/tex] so let [tex][\bar a]=\{k\bar a:k\in Z\}=\{ka+k(rm):r,k\in Z\}[/tex] in particular let [tex] u\in [\bar a][/tex] so, [tex]u=ak+k(rm)[/tex]

So, this would mean that any linear combination of a and m is also in a+[m]. Now since

1=ax+my, i am saying that [tex]1\in a+[m]=\bar a[/tex]

ok let's stop here, cuz, i lost my stream of thought!

Any hints, ideas, would be greatly appreciated.
Phys.Org News Partner Science news on Phys.org
'Smart material' chin strap harvests energy from chewing
King Richard III died painfully on battlefield
Capturing ancient Maya sites from both a rat's and a 'bat's eye view'
sutupidmath
#2
Nov20-08, 12:55 AM
P: 1,633
Well, i know the previous post is way too long, so if you don't have time to have a look at it, the whole thing is about the following:

Prove that
[tex]\bar a[/tex] is a generator of the additive group [tex]Z_m[/tex] if and only if gcm(m,a)=1.
sutupidmath
#3
Nov20-08, 07:51 PM
P: 1,633
Nevermind, i figuret it out. Thnx though!


Register to reply

Related Discussions
Additive probabilities Set Theory, Logic, Probability, Statistics 6
Multiplicative and additive fitness Biology 0
What is an additive constant? Introductory Physics Homework 5
Additive functions Calculus 7
Additive moments of inertia? Introductory Physics Homework 7