Hi all,(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Generator of the additive gr. Z_m

**Physics Forums | Science Articles, Homework Help, Discussion**