Proof check (I swear, if I ever misclick again...)

[Boi]

View attachment 39388
I'll be using [imath]o(g)[/imath] to denote the order of an element [imath]g[/imath], [imath]e[/imath] to denote the neutral element and [imath]\langle g \rangle[/imath] to denote the cyclic group of [imath]g[/imath].
For the proof I'll have to prove 2 lemmas first (they're very obvious results, but they are not stated in the book, so I've felt the need to prove them).
Lemma 1: If [imath]G[/imath] is a group, [imath]g \in G[/imath], [imath]o(g) = n[/imath], [imath]p, q \in \mathbb{Z}[/imath] and [imath]p \equiv q \; (\mathrm{mod} \; n)[/imath], then [imath]g^{p}=g^{q}[/imath].
Proof of Lemma 1: if [imath]p \equiv q \; (\mathrm{mod} \; n)[/imath], then, by defenition of congruence modulo n, [imath]p-q=kn[/imath], where [imath]k[/imath] is an integer. It follows that [imath]p = q+kn[/imath]. So, [math]g^{p}=g^{q+kn}=g^{q} \cdot g^{kn}=g^{q} \cdot (g^{n})^{k}=g^{q}\cdot e^{k}=g^{q}[/math].
Lemma 2: If [imath]n, m \in \mathbb{Z}[/imath], [imath]d=\mathrm{gcd}(n, m)[/imath], [imath]n_0=\frac{n}{d}[/imath] and [imath]m_0=\frac{m}{d}[/imath], then [imath]n_0[/imath] and [imath]m_0[/imath] are coprime.
Proof of Lemma 2: suppose the opposite is true: [imath]n_0[/imath] and [imath]m_0[/imath] are not coprime and they have a common divisor [imath]f>1[/imath]. So, [imath]n_0=fs[/imath] and [imath]m_0=fr[/imath] ([imath]s[/imath] and [imath]r[/imath] are integers). By "unwrapping" the definitions of [imath]n_0[/imath] and [imath]m_0[/imath] and multiplying by [imath]d[/imath] on both sides we get [imath]n = dfs[/imath] and [imath]m=dfr[/imath]. Now we have reached a contradiction: we assumed [imath]d[/imath] to be the greatest common divisor of [imath]n[/imath] and [imath]m[/imath], but [imath]D=df[/imath] clearly divides both [imath]n[/imath] and [imath]m[/imath] without dividing [imath]d[/imath] (since we assumed [imath]f>1[/imath]).
The proof itself: Without the loss of generality I am going to assume that [imath]m \ge n[/imath]. I'll denote the element of order [imath]n[/imath] by [imath]a[/imath] and the element of order [imath]m[/imath] by [imath]b[/imath]. Since [imath]G[/imath] is abelian, for all [imath]j \in \mathbb{Z}[/imath] [imath](ab)^{j}=a^{j}b^{j}[/imath]. By using Lemma 1 we can represent every element of [imath]\langle ab \rangle[/imath] with a pair of integers [imath](x, y)[/imath], [imath]0 \le x \le n-1[/imath], [imath]0 \le y \le m-1[/imath] and for which ther exists such an integer [imath]z[/imath], that [imath]z \equiv x \; (\mathrm{mod} \; n)[/imath] [imath]z \equiv y\; (\mathrm{mod} \; m)[/imath]. I want to replace the last requirement with the following: [imath]x[/imath] and [imath]y[/imath] must be congruent modulo [imath]d[/imath] (where [imath]d= \mathrm{gcd}(n, m)[/imath]). Let me show that these are equivalent.
[imath]\Rightarrow[/imath]
If [imath]z \equiv x \; (\mathrm{mod} \; n)[/imath] and [imath]z \equiv y \; (\mathrm{mod} \; m)[/imath], then [imath]z=x+nu[/imath] and [imath]z=y+mv[/imath], so [imath]x+nu=y+mv[/imath] ([imath]u,v \in \mathbb{Z}[/imath]. It follows that [imath]x-y=mv-nu[/imath]. If we pull out [imath]d[/imath] from [imath]n[/imath] and [imath]m[/imath] we get [imath]x-y=d(m_0v-n_0u)=dh[/imath]. Hence [imath]x \equiv y \; (\mathrm{mod} \;d)[/imath].
[imath]\Leftarrow[/imath]
If [imath]x \equiv y \; (\mathrm{mod} \; d)[/imath], then [imath]x-y=dh[/imath], [imath]h \in \mathbb{Z}[/imath]. Now, using Lemma 2 and Bezout's identity we get [imath]1=n_0u+m_0v[/imath]. Substituting [imath]u=-t[/imath] and multiplying both sides by [imath]h[/imath] we get [imath]h=m_0v-n_0t[/imath]. So, [imath]x-y=dh=d(m_0v-n_0t)=mv-nt \Rightarrow x+nt=y+mv[/imath]. Letting [imath]z=x+nt[/imath] we get the exact [imath]z[/imath] we need.
With the change of the last requirement it's easier to count the elements of [imath]\langle ab \rangle[/imath]. Let's first choose [imath]x[/imath]. Remembering our constraints ([imath]0 \le x \le n-1[/imath]) we have [imath]n[/imath] choices for [imath]x[/imath]. Now, to count choices for [imath]y[/imath] let me first the number of choices for [imath]y[/imath] when [imath]x=0[/imath]. If [imath]x=0[/imath], then [imath]y[/imath] should take the form [imath]dk[/imath] to meet the condition. There would be [imath]\frac{m}{d}[/imath] such choices ([imath]0, \;d, \; 2d, \; ...\: , (\frac{m}{d}-1)d[/imath]). When [imath]0 < x[/imath], we can just shift all these numbers by [imath]x[/imath]... except for the larger ones. Well, to not change the total number of choices for [imath]y[/imath] we should make a new valid choice for every failed one. So, if [imath]m-1 < x+ds[/imath], then [imath]d(m_0-s)-1 < x \Rightarrow -1 < x- d(m_0-s)[/imath]. Because [imath]x-d(m-0-s)[/imath] is an integer, we can change the last inequality to [imath]0 \le x-d(m_0-s)[/imath], making [imath]x-d(m_0-s)[/imath] a viable choice for [imath]y[/imath]. Finally, we have [imath]n[/imath] choices for [imath]x[/imath], [imath]\frac{m}{d}[/imath] choices for y, giving us a total of [imath]\frac{nm}{d}[/imath] or [imath]\mathrm{lcm}(n, m)[/imath] elements in [imath]\langle ab \rangle[/imath]. [imath]\langle ab \rangle[/imath] having [imath]\mathrm{lcm}(n, m)[/imath] means that [imath]ab[/imath], an element of [imath]G[/imath], has order [imath]\mathrm{lcm}(n, m)[/imath]. QED.
I hope it's comprehensible.

 

[fresh_42]

For the record. The statement is:

Let [imath] G [/imath] be an abelian group, and suppose [imath] G [/imath] has elements of order [imath] n [/imath] and [imath] m[/imath]; then there is an element of order the least common multiple of [imath] n[/imath] and [imath] m. [/imath]

The proofs of the lemmas are correct, but you lost me in the proof of the statement when [imath] x,y [/imath] came into play. I think it is way too complicated. We have the equation [imath] \operatorname{gcd}(n,m)\cdot \operatorname{lcm}(n,m)=n\cdot m. [/imath] Now, use this and your remark that [imath] (ab)^j=a^j b^j [/imath] and calculate [imath] (ab)^{\operatorname{lcm}(n,m)}. [/imath]

 

[Boi]

We have the equation [imath] \operatorname{gcd}(n,m)\cdot \operatorname{lcm}(n,m)=n\cdot m. [/imath] Now, use this and your remark that [imath] (ab)^j=a^j b^j [/imath] and calculate [imath] (ab)^{\operatorname{lcm}(n,m)}. [/imath]

Okay, I'll try to do that. I'll come back once I succeed.
But also, even if the proof is overcomplicated, is it correct?

 

[fresh_42]

Okay, I'll try to do that. I'll come back once I succeed.
But also, even if the proof is overcomplicated, is it correct?

As I already said, you lost me with the introduction of [imath] x,y.[/imath] What are they? How are they determined, and why is [imath] x\equiv y\pmod{nm}, [/imath] and last but not least, how do they "represent" [imath] ab [/imath]?

 

[Boi]

As I already said, you lost me with the introduction of [imath] x,y.[/imath] What are they?

how do they "represent" [imath] ab [/imath]?

So, any element of [imath]\langle ab \rangle[/imath] is [imath]ab[/imath] raised to some integer power [imath]z[/imath]. Because [imath]G[/imath] is abelian, we have [imath](ab)^{z}=a^{z}b^{z}[/imath]. Now, if we reduce [imath]z[/imath] modulo [imath]n[/imath] (for [imath]a[/imath]) and modulo [imath]m[/imath] (for [imath]b[/imath]) we would get [imath]a^{x}b^{y}[/imath] where [imath]0 \le x \le n-1[/imath], [imath]0 \le y \le m-1[/imath], [imath]z \equiv x \; (\mathrm{mod} \; n)[/imath] and [imath]z \equiv y \; (\mathrm{mod} \; m)[/imath]. This is where [imath]x[/imath] and [imath]y[/imath] come from and how they "represent" an element of [imath]\langle ab \rangle[/imath].

why is x≡y(modnm), x\equiv y\pmod{nm}, x≡y(modnm)

I don't know where you got that congruence from.
Btw, thanks for your suggested way of solving the task, it seems much cleaner, although I hadn't wrote the proof with it yet

 

[fresh_42]

Btw, thanks for your suggested way of solving the task, it seems much cleaner, although I hadn't wrote the proof with it yet

It is only one line with maximal three equality signs. Plus the equation [imath] nm=\operatorname{gcd}(n,m)\operatorname{lcm}(n,m) [/imath] of course. So if you want to prove something, you should prove that equation.

 

[Boi]

only one line with maximal three equality signs

well, maybe not tha clean.([imath]o(a)=n, \: o(b)=m, \: d=\mathrm{gcd}(n, m), \: n_0=\frac{n}{d}, \: m_0=\frac{m}{d}[/imath]) I mean, sure [math](ab)^{\mathrm{lcm}(n, m)}=a^{nm_0}b^{n_0m}=(a^{n})^{m_0}(b^{m})^{n_0}=e[/math] But that does not meant that [imath]o(ab)=\mathrm{lcm}(n, m)[/imath].

 

[fresh_42]

Some remarks on your proof.

• It would have been clearer if you had used either [imath] j [/imath] or [imath] z [/imath] and explained it as in your last post. I still have trouble dealing with those many variables.
• "Should" should not occur in a proof. Readers do not want to read what should be, only what is. That's why many proofs are scribbled one way but written down backward. If you say "should," then I either stop reading or scribble the possible cases myself. And that's painful, particularly with those many variables. I'm currently stuck at your first "should". It asks me "why should it be?" and "what may I assume as given and what as assumed?"
• Greater than or less than shouldn't occur at all. We only need integers because it is about divisibility, and signs don't matter.
• I think you did the same thing as in my line of equations, only more complicated.

 

[fresh_42]

well, maybe not tha clean.([imath]o(a)=n, \: o(b)=m, \: d=\mathrm{gcd}(n, m), \: n_0=\frac{n}{d}, \: m_0=\frac{m}{d}[/imath]) I mean, sure [math](ab)^{\mathrm{lcm}(n, m)}=a^{nm_0}b^{n_0m}=(a^{n})^{m_0}(b^{m})^{n_0}=e[/math] But that does not meant that [imath]o(ab)=\mathrm{lcm}(n, m)[/imath].

It goes as follows:
[math] (ab)^{\operatorname{lcm}(n,m)}=a^{\operatorname{lcm}(n,m)}b^{\operatorname{lcm}(n,m)}=\left(a^n\right)^{\frac{m}{\operatorname{gcd}(n,m)}}\left(b^m\right)^{\frac{n}{\operatorname{gcd}(n,m)}}=\left(e\right)^{\frac{m}{\operatorname{gcd}(n,m)}}\left(e\right)^{\frac{n}{\operatorname{gcd}(n,m)}}=e. [/math]which means [imath] o(ab)\,|\,\operatorname{lcm}(n,m). [/imath]

And, yes, you are right. We also need to show that [imath] \operatorname{lcm}(n,m)\,|\,o(ab). [/imath]

 

[fresh_42]

Here is my version:

If [imath] o(ab)\,|\,\operatorname{lcm}(n,m) [/imath] then
[math]\begin{array}{lll} o(ab)&=q\cdot\operatorname{lcm}(n,m)=sn=tm\\[10pt] e&=(ab)^{o(a,b)}=a^{o(a,b)}b^{o(a,b)}=a^{tm}=b^{sn}\\[10pt] &\Longrightarrow o(a)=n\,|\,tm=o(a,b)\wedge o(b)=m\,|\,sn=o(a,b)\\[10pt] &\Longrightarrow \operatorname{lcm}(n,m)\,|\,o(a,b) \end{array}[/math]
I hope this is correct.