- #1
sutupidmath
- 1,630
- 4
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 let's 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 let's 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.
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 let's 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 let's 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.