Math Challenge - August 2019

[nuuskur]

Spoiler

The fundamental theorem of abelian groups says that for any finite abelian group

$$A \cong \mathbb Z_{p_1^{k_1}} \oplus \ldots \oplus \mathbb Z_{p_m^{k_m}}$$
Hyperlinking breaks my raw text for some reason. I'll be using Sylow's theorems which I will refer to as theorems 1, 2 and 3 respectively. (https://en.wikipedia.org/wiki/Sylow_theorems)

Spoiler: Problem 5 - order 6

In the abelian case there are $\mathbb Z_6\cong\mathbb Z_2\oplus\mathbb Z_3$.

Quick remark. Being a Sylow $p-$subgroup is invariant with respect to conjugating, thus if $H$ was a unique Sylow $p-$subgroup, we would have $gHg^{-1} = H, g\in G,$ i.e $H$ would be normal.

Fact. Suppose a non-abelian group $G$ has order $pq$ (primes) with $q\equiv 1 \pmod{p}$, then there are precisely $q$ Sylow $p-$subgroups in $G$.

Proof of fact. Let $n_p,n_q$ be the numbers of Sylow $p,q-$subgroups respectively. By assumption $q>p$. By theorem 3 $n_q \equiv 1 \pmod{q}$ and by theorem 1 $n_q\mid p$, which forces $n_q = 1$, thus we have a (normal) subgroup of order $q$, which makes it cyclic, therefore abelian.

For $n_p$ we thus have two choices: $n_p = 1,q$. If $n_p = 1$, then $G\cong \mathbb Z_p \oplus \mathbb Z_q$ would be abelian, thus it must be that $n_p = q$.

Our non-abelian group $G$ therefore contains three Sylow $2-$subgroups, call them $H_1,H_2,H_3$, which by theorem 2 are all conjugate to each other. We have $\mbox{Sym}(H_1,H_2,H_3) \cong S_3$. We show that $G\cong S_3$. Define
$$\varphi : G\to \mbox{Sym}(H_1,H_2,H_3), \quad\varphi (g)(H_j) := gH_jg^{-1}$$
(also called conjugating)

Spoiler: well-defined, morphism

Firstly, if $H$ is a Sylow $p-$subgroup, then conjugating it gives another Sylow $p-$subgroup, hence it must hold that $gH_ig^{-1} = H_j$ for some $j$.

The map $\varphi (g)$ is injective, because if $gH_ig^{-1} = gH_jg^{-1}$, then
$$h_i \in H_i \Rightarrow gh_ig^{-1} \in gH_ig^{-1} = gH_jg^{-1} \Rightarrow h_i \in H_j.$$
The argument is symmetrical, thus $H_i=H_j$. It is surjective due to finiteness.

Take $g,h\in G$, then
$$\varphi (gh) (H_j) = (gh)H_j(gh)^{-1} = g(hH_jh^{-1})g^{-1} = g (\varphi (h)(H_j)) g^{-1} = \varphi (g) (\varphi (h)(H_j)) = (\varphi (g) \varphi (h))(H_j).$$

To show it's an isomorphism, it suffices to show it's injective (because $|G| = |S_3| = 6$). Suppose $\varphi (g) = \mbox{id}$ i.e $gH_jg^{-1}=H_j$, then by definition $g\in N(H_j)$ the normaliser of $H_j$. If $N(H_j) = G$, then $H_j$ would be normal, which would then make it equal to its conjugates, contradicting the fact that there are three Sylow $2-$subgroups.

Therefore, all $N(H_j) = H_j$ and $g\in H_1\cap H_2\cap H_3 = \{e\}$ i.e $g=e$, which makes $\varphi$ an isomorphism.

Typo

Spoiler: "typo"

By theorem 3 $n_q \equiv 1 \pmod{q}$ and by theorem 3 $n_q\mid p$

As a continuation to #73.

Spoiler: Problem 5 - order 8

In the abelian case there are
$$\mathbb Z_8 \qquad \mathbb Z_4 \oplus \mathbb Z _2 \qquad \mathbb Z_2 \oplus\mathbb Z_2\oplus\mathbb Z_2$$
Suppose $G$ is non-abelian of order $8$. If there is an element of order 8, then $G$ is cyclic, thus abelian. Suppose the maximal order is $2$ and pick $g,h\in G$. If $gh=e$, then they commute. Suppose $(gh)^2 = e$, then
$$gh = geh = g(ghgh)h = (gg)hg(hh) = ehge = hg$$
and again $G$ would be abelian. Thus we must have an element $a$ of order $4$. Its generated subgroup $\langle a \rangle =: H$ is of index $2$, therefore normal. Take $b\notin H$, then we have $bab^{-1}\in H$ due to normality. Notice that
$$(bab^{-1})^4 = bab^{-1}bab^{-1}bab^{-1}bab^{-1} = baaaab^{-1} = e.$$
If also $(bab^{-1}) ^2 = e$, then $baab^{-1} = e$ would lead to $aa=e$, contradicting the order of $a$.
Next, we find the possible values of $bab^{-1}$.

1. If $bab^{-1} = a^4 = e$, then $a=e$, which is impossible.
2. If $bab^{-1} = a$, then $ba = ab$, but this will make $G$ abelian. Indeed, pick $g,h\in G$. If they're both in $H$, then they commute. Suppose $g\notin H$ and write $g = ba^m$ and $h = a^n$, then
   $$gh = ba^ma^n = ba^na^m = a^n ba^m = hg.$$
   and if both reside outside $H$, then writing $g = ba^m$ and $h = ba^n$ would similarly lead to $gh=hg$. But our group is not abelian.
3. If $bab^{-1} = a^2$, then $(bab^{-1})^2 = e$ would contradict the order of $bab^{-1}$.

Thus, the only possibility is $bab^{-1}=a^3 =a^{-1}$.

There are two cases to consider.

1. $b$ is of order $2$, then we have $G \cong \langle a,b \mid \mbox{ord}(a) = 4, \mbox{ord}(b) = 2, bab^{-1} = a^{-1} \rangle$ this is the dihedral group $D_8$.
2. $b$ is of order $4$. We show $G$ is the dicyclic group $\mbox{Dic}_2$, where
   $$\mbox{Dic}_2 \cong \langle x,y \mid x^{4} = e, x^2 = y^2, x^{-1} = y^{-1}xy \rangle.$$
   Notice that
   $$bab^{-1} = a^{-1} \Rightarrow b^{-1}ab = b^{-1}(ba^{-1}b^{-1})b = a^{-1}.$$
   So we have left to show $a^2 = b^2$. Considering the natural projection $G\to G/H\cong\mathbb Z_2$, we have $b^2 \in H$. Consider possible values of $b^2$.
   1. $b^2 = a^4 = e$ contradicts order of $b$.
   2. $b^2 = a$ contradicts order of $a$
   3. $b^2 = a^2$ is what we want.
   4. $b^2 = a^{-1}$ contradicts order of $a^{-1}$ (hence order of $a$).
      Thus $b^2 = a^2$ must hold.

 

[etotheipi]

Spoiler: Problem 13

Is the answer 70km?

 

[fresh_42]

Spoiler: Problem 13

Is the answer 70km?

Yes, but what is the calculation?

 

[etotheipi]

Yes, but what is the calculation?

Spoiler: Problem 13

Let the distance outside the town be d

The initial average speed before the change of heart is thus $$v_1 = \frac {d+10} {0.25 + \frac{d}{180}},$$
In a similar vein the average speed after the driver decides to lower his speeds is
$$v_2 = \frac {d+10} {0.5 + \frac{d}{160}},$$
We are told that the difference between these two speeds is 40kmh, so we solve the following equation for d
$$\frac {d+10} {0.25 + \frac{d}{180}} = \frac {d+10} {0.5 + \frac{d}{160}} + 40$$
Cleaning up that mess gives a quadratic
$$d^2 - 120d + 3600 = 0$$
which yields a single solution of d=60. Hence the total distance is d+10 = 70.

 

[Not anonymous]

13. David drives to work every working day by car. Outside towns he drives at an average speed of $180\,\text{km/h}$. On the
$10\,\text{km}$ in town, he drives at an average speed of $40\,\text{km/h}$. As a result, he is often too fast and gets a ticket. Meanwhile he has realized that things can not go on like this and he decides to reduce his average speed by $20\,\text{km/h}$ in town as well as outside. How long is his way to work, if this reduces his average speed by $40\,\text{km/h}$ on total?

Spoiler: Q13

The total distance to work is 70 km, including the 10 km inside the town (which is given).

Let $d$ be the distance traveled outside the town when David goes to work. Then his original average speed would be $$s_1 = \frac {(d + 10)} {\frac {d} {180} + \frac {10} {40}}$$. After reducing the speeds inside and outside the towns by $20 km/h$ each, the new average speed becomes $$s_2 = \frac {(d + 10)} {\frac {d} {160} + \frac {10} {20}}$$

Given that the new average speed is lower than the previous average speed by $40km/h$, we get $$s_1 - s_2 = 40 \Rightarrow \frac {(d + 10)} {\frac {d} {180} + \frac {10} {40}} - \frac {(d + 10)} {\frac {d} {160} + \frac {10} {20}} = 40$$

The above equation reduces to $(d - 60)^2 = 0$, giving $d = 60$

P.S.
Thanks for giving 1 simple question that I could solve confidently . But more thanks for the tough questions for which I couldn't not solve - I am keen to learn from the solutions posted by others and from the learning resources.

 

[fresh_42]

Spoiler: Q13

The total distance to work is 70 km, including the 10 km inside the town (which is given).

Let $d$ be the distance traveled outside the town when David goes to work. Then his original average speed would be $$s_1 = \frac {(d + 10)} {\frac {d} {180} + \frac {10} {40}}$$. After reducing the speeds inside and outside the towns by $20 km/h$ each, the new average speed becomes $$s_2 = \frac {(d + 10)} {\frac {d} {160} + \frac {10} {20}}$$

Given that the new average speed is lower than the previous average speed by $40km/h$, we get $$s_1 - s_2 = 40 \Rightarrow \frac {(d + 10)} {\frac {d} {180} + \frac {10} {40}} - \frac {(d + 10)} {\frac {d} {160} + \frac {10} {20}} = 40$$

The above equation reduces to $(d - 60)^2 = 0$, giving $d = 60$

P.S.
Thanks for giving 1 simple question that I could solve confidently . But more thanks for the tough questions for which I couldn't not solve - I am keen to learn from the solutions posted by others and from the learning resources.

There are only a couple of rules to attack a problem, if there is no direct, computational approach:

• simplify it
• get rid of what disturbs
• find and use symmetries

E.g. problems with rational numbers are also problems with integers, What does it say in the integer case? Integer problems are often solved by looking at the remainders modulo one or more primes: If there is an integer solution, then there is a solution with remainders, too.
$x^2+y^2=z^2 \Longrightarrow x^2+y^2\equiv z^2 \mod 2 \Longrightarrow \{\,x,y,z\,\} \text{ contains at least one even number }$ because not all $x,y,z$ can be odd, since this would give $1+1=1$ for the remainders.

If there are disturbing denominators, multiply them off.

If there are symmetries, find other symmetric expressions and investigate whether there are relations.

 

[Not anonymous]

There are only a couple of rules to attack a problem, if there is no direct, computational approach:

• simplify it
• get rid of what disturbs
• find and use symmetries

E.g. problems with rational numbers are also problems with integers, What does it say in the integer case? Integer problems are often solved by looking at the remainders modulo one or more primes: If there is an integer solution, then there is a solution with remainders, too.
$x^2+y^2=z^2 \Longrightarrow x^2+y^2\equiv z^2 \mod 2 \Longrightarrow \{\,x,y,z\,\} \text{ contains at least one even number }$ because not all $x,y,z$ can be odd, since this would give $1+1=1$ for the remainders.

If there are disturbing denominators, multiply them off.

If there are symmetries, find other symmetric expressions and investigate whether there are relations.

Hi @fresh_42 , thanks for the tips. In that example, when you say $x^2 + y^2 \equiv z^2 \mod 2$ did you mean to say $(x^2 + y^2) \mod 2 \equiv z^2 \mod 2$?

 

[Not anonymous]

2. Find the equation of a curve such that $y''$ is always $2$ and the slope of the tangent line is $10$ at the point $(2,6)$.

Spoiler: Question 2

Is the answer $y = x^2 + 6x - 10$?

$y'' = 2 \Rightarrow y' = \int y'' \, dx = \int 2 \,dx = (2x + a)$, where $a$ is some constant
$y = \int (2x + a) \, dx = (x^2 + ax + b)$ where $b$ is some constant

Since slope of tangent at $x = 2$ is 10, we get $y'_{(x=2)} = 2 \Rightarrow 2 \times 2 + a = 10 \Rightarrow a = 6$

Since $(2, 6)$ is a point on the curve, $y_{(x=2)} = 6 \Rightarrow (x^2 + 6x + b)_{(x=2)} = 6 \Rightarrow 4 + 12 + b = 10 \Rightarrow b = -6$

 

[Not anonymous]

1. The maximum value of $f$ with $f(x) = x^a e^{2a - x}$ is minimal for which values of positive numbers $a$ ?

Spoiler: Question 1

Is the answer $a = e^{-2}$?

Here is the calculation I used - $f'(x) = ax^{a-1} e^{2a - x} - x^a e^{2a - x} = x^{a-1} e^{2a - x} (a - x)$
At the maximal point, $f'(x) = 0 \Rightarrow x=a$ or $x=0$. I have not worked out a rigorous proof for maximality at $a$, but it can be seen that since when $x > a$, $f'(x) < 0$, $f(a) > 0$ (given $a > 0$), $x = a$ must be the global maximum.

Therefore, maximum value of $f$ is $a^a e^a$, which we will now denote by $g(a)$, a function of variable $a$. Obviously, for $a > 0$, this expression will not have a finite maximum, since as $a \rightarrow \inf$, $f(a) \rightarrow \inf$. Only a finite minimum would be possible and at the minimal point $g'(a) = 0$. To simplify differentiation, we may apply logarithm on the expression to find the minimum, which is valid for $a > 0$ since logarithm is a monotonically increasing function. $h(a) = \ln g(a) = a \ln a + a$. At the minimal point, $h' = 0 \Rightarrow 2 + \ln a = 0 \Rightarrow a = e^{-2}$

 

[fresh_42]

Hi @fresh_42 , thanks for the tips. In that example, when you say $x^2 + y^2 \equiv z^2 \mod 2$ did you mean to say $(x^2 + y^2) \mod 2 \equiv z^2 \mod 2$?

Yes, except the correct notation is $a \equiv b \mod 2$ or $a=b \mod 2$ The module automatically covers the entire equation. It is basically a function from $\mathbb{Z}$ to $\mathbb{Z}/\mathbb{2Z}=\mathbb{Z}_2=\{\,0,1\,\}$. So $\mod n$ means to apply this function on both sides, otherwise it wouldn't make sense.

 

[Pi-is-3]

Spoiler: Q14

$2x^6+3y^6=z^3$

It suffices to prove that $2x^3+3y^3=1$ has no rational roots (expression obtained by dividing by $z^3$ ).

We see that $\frac{3y^3}{2} = \frac{1}{2} -x^3$

We see that $x^3= \frac{1}{2} - t^3$ and $y= \frac{2t^3}{3}$

If t is rational, then y is irrational. If t is irrational, then x is irrational. Hence there are no solutions for x and y in rationals.

 

[fresh_42]

$2x^6+3y^6=z^3$

It suffices to prove that $2x^3+3y^3=1$ has no rational roots (expression obtained by dividing by $z^3$ ).

Prove it!

 

[Pi-is-3]

1. The maximum value of $f$ with $f(x) = x^a e^{2a - x}$ is minimal for which values of positive numbers $a$ ?

Spoiler: Question 1

Is the answer $a = e^{-2}$?

Here is the calculation I used - $f'(x) = ax^{a-1} e^{2a - x} - x^a e^{2a - x} = x^{a-1} e^{2a - x} (a - x)$
At the maximal point, $f'(x) = 0 \Rightarrow x=a$ or $x=0$. I have not worked out a rigorous proof for maximality at $a$, but it can be seen that since when $x > a$, $f'(x) < 0$, $f(a) > 0$ (given $a > 0$), $x = a$ must be the global maximum.

Therefore, maximum value of $f$ is $a^a e^a$, which we will now denote by $g(a)$, a function of variable $a$. Obviously, for $a > 0$, this expression will not have a finite maximum, since as $a \rightarrow \inf$, $f(a) \rightarrow \inf$. Only a finite minimum would be possible and at the minimal point $g'(a) = 0$. To simplify differentiation, we may apply logarithm on the expression to find the minimum, which is valid for $a > 0$ since logarithm is a monotonically increasing function. $h(a) = \ln g(a) = a \ln a + a$. At the minimal point, $h' = 0 \Rightarrow 2 + \ln a = 0 \Rightarrow a = e^{-2}$

One wrong assumption, x=a is not the global maximal for all a. If a is negative or an even natural number, then it is just a critical point. But the answer is correct because it is the global maxima of $e^{-2}$.

 

[Pi-is-3]

Prove it!

Sorry, I thought it was sufficient to leave it at that.

Spoiler: Proof continued

Let $x^2=a, y^2=b$.
Then we have $3a^3+2b^3=z^3$

Let $\frac{a}{z}=j$ and $\frac{b}{z}=k$

If x,y,z are rational, then so are j and k.

Finally, if their are no rational solutions of j and k, then their are no rational solutions for x,y,z.

This is why it suffices to prove that $3j^3+2k^3=1$ has no rational solutions.

EDIT: I made one more mistake, I didn't mention that z is not equal to 0. If z=0, then the answers come to be (0,0,0) which is excluded.

 

[fresh_42]

Sorry, I thought it was sufficient to leave it at that.

No. It is a bad habit and a common place to hide mistakes.

You have to show that a solution of the general version provides a solution for the restricted one. So let us assume we have a solution $(r,s,t)$ such that $2r^6 +3s^6=t^3$.

From $t=0$ we obtain the trivial solution only, since the left hand side is nonnegative.
For $t\neq 0$ we get $2 \left( \dfrac{r}{t} \cdot r \right)^3\cdot 3 \left( \dfrac{s}{t} \cdot s\right)^3=1\,.$

 

[fresh_42]

You are hard to follow.

$2x^6+3y^6=z^3$

It suffices to prove that $2x^3+3y^3=1$ has no rational roots (expression obtained by dividing by $z^3$ ).

Done in post #89, although the additional variables make it unnecessarily complicated (see post #90).

We see that $\frac{3y^3}{2} = \frac{1}{2} -x^3$

We see that $x^3= \frac{1}{2} - t^3$ and $y= \frac{2t^3}{3}$

We do not "see" it. What we see is that you invented out of the blue a certain number $t$. What you should have done is telling us, that you set $t:= \sqrt[3]{\frac{3}{2}y} \in \mathbb{R}$ such that $y=\frac{2}{3}t^3$. But now $x^3\neq \frac{1}{2}-t^3$.

To correct this, we have to set $t:=\sqrt[3]{\frac{3}{2}}y$. Now $x^3= \frac{1}{2}-t^3$.

If t is rational, then y is irrational.

How that?

If t is irrational, then x is irrational. Hence there are no solutions for x and y in rationals.

 

[Math_QED]

Proof of fact. Suppose $S\in\Sigma$ has property $(P)$. Then $\Sigma _S$ is an infinite sub sigma algebra. Pick $T \in \Sigma _S \setminus \{\emptyset, S\}$ Write $S= T\cup (S\cap T^c)$. By (E) at least one of the respective sub sigma algebras must be infinite.

First of all, sorry for the late reply. I'm trying to understand this part of your answer. I guess you want to show that either $\Sigma_T$ or $\Sigma_{S \cap T^c}$ has property $(P)$, right?

Can you please explain me why the following sentence is true?

"By (E) at least one of the respective sub sigma algebras must be infinite."

 

[nuuskur]

Can you please explain me why the following sentence is true?

"By (E) at least one of the respective sub sigma algebras must be infinite."

If $\Sigma _T \cup \Sigma _{S\cap T^c}$ was a finite set, then their generated sub sigma algebra, which is $\Sigma _S$, would also be finite.

I guess you want to show that either $\Sigma_T$ or $\Sigma_{S \cap T^c}$ has property $(P)$, right?

They can both have that property, too.

 

[Not anonymous]

8. Show that there is no triple $(a,b,c) \in \mathbb{Z}^3\setminus \{(0,0,0)\}$ such that $a^2 + b^2 = 3 c^2$.

After spending a few seconds thinking about it, I realized that this problem is much simpler than what I had imagined when I first came across this question in the challenge list. An interesting problem nevertheless for people like me who have never had the opportunity to a course in number theory and the like and want some warm-up questions before moving to tougher problems.

I think there might be a simpler proof than what I came up with.

Spoiler: A solution for question 8

Since $a^2 + b^2 = 3 c^2$, it must be the case that $a^2 + b^2 \equiv 0 \mod 3$. Since $(x + y) \mod n = x \mod n + y \mod n)$, we consider all possible combinations of $a \mod 3$ and $b \mod 3$ and find their effect on $a^2 \mod 3 + b^2 \mod 3$. We only need to consider the modulo pairs (0, 0), (0, 1), (0, 2), (1, 1), (1, 2) and (2, 2) for the modulos of a and b, since the remaining cases like (2, 1) are symmetric. And we use the observation that if $x \equiv k \mod n$, then $x^2 \equiv k^2 \mod n$ (since $x = pn + k$ for some integer $p$ and $x^2 = (p^2 n^2 + k^2 + 2kpn) \equiv k^2 \mod n$).

$$
\begin{array}{|c|c|c|c|c|}
\hline a \mod 3 & b \mod 3 & a^2 \mod 3 & b^2 \mod 3 & (a^2 + b^2) \mod 3 \\
\hline 0 & 0 & 0 & 0 & 0 \\
\hline 0 & 1 & 0 & 1 & 1 \\
\hline 0 & 2 & 0 & 1 & 1 \\
\hline 1 & 1 & 1 & 1 & 2 \\
\hline 1 & 2 & 1 & 1 & 2 \\
\hline 2 & 2 & 1 & 1 & 2 \\
\hline
\end{array}
$$

So the only case where $(a^2 + b^2) \mod 3 = 0$ is when the LHS modulo pair is (0, 0), i.e. both a and b are multiples of 3, say $a = 3A, b = 3B$ for some non-zero integers $A, B$ (since question states a, b, c are all non-zero). Using this in the original expression, we get $a^2 + b^2 = 9A^2 + 9B^2 = 3 c^2 \Rightarrow A^2 + B^2 = \frac {c^2} {3}$

Since $A^2 + B^2$ and hence $\frac {c^2} {3}$ is an integer, and $c$ is an integer and 3 is prime, it must be the case that $c$ too is a multiple of 3, say $c = 3C$ for some non-zero integer $C$. So the above equivalence becomes, $A^2 + B^2 = \frac {9C^2} {3} = 3C^2$, which is of the same for as the original equation. So as long as the 2 integers on LHS are multiples of 3, we can reduce the expression to another expression of the same form but with the absolute values of the integers becoming smaller. This cannot continue infinitely, implying that we will reach a point where at least one of the 2 integers is no longer a multiple of 3, meaning that the modulo pair is no longer (0, 0). And for any such non-(0, 0) pair, we already showed that the RHS cannot be a multiple of 3, but this contradicts the expression from that required the RHS to be a multiple of 3. Therefore, the only remaining possibility, i.e. of having an LHS module pair of the form (0, 0) that also satisfies the expression form $a^2 + b^2 = 3 c^2$, too is ruled out. Hence proved.

 

[Math_QED]

8. Show that there is no triple $(a,b,c) \in \mathbb{Z}^3\setminus \{(0,0,0)\}$ such that $a^2 + b^2 = 3 c^2$.

After spending a few seconds thinking about it, I realized that this problem is much simpler than what I had imagined when I first came across this question in the challenge list. An interesting problem nevertheless for people like me who have never had the opportunity to a course in number theory and the like and want some warm-up questions before moving to tougher problems.

I think there might be a simpler proof than what I came up with.

Spoiler: A solution for question 8

Since $a^2 + b^2 = 3 c^2$, it must be the case that $a^2 + b^2 \equiv 0 \mod 3$. Since $(x + y) \mod n = x \mod n + y \mod n)$, we consider all possible combinations of $a \mod 3$ and $b \mod 3$ and find their effect on $a^2 \mod 3 + b^2 \mod 3$. We only need to consider the modulo pairs (0, 0), (0, 1), (0, 2), (1, 1), (1, 2) and (2, 2) for the modulos of a and b, since the remaining cases like (2, 1) are symmetric. And we use the observation that if $x \equiv k \mod n$, then $x^2 \equiv k^2 \mod n$ (since $x = pn + k$ for some integer $p$ and $x^2 = (p^2 n^2 + k^2 + 2kpn) \equiv k^2 \mod n$).

$$
\begin{array}{|c|c|c|c|c|}
\hline a \mod 3 & b \mod 3 & a^2 \mod 3 & b^2 \mod 3 & (a^2 + b^2) \mod 3 \\
\hline 0 & 0 & 0 & 0 & 0 \\
\hline 0 & 1 & 0 & 1 & 1 \\
\hline 0 & 2 & 0 & 1 & 1 \\
\hline 1 & 1 & 1 & 1 & 2 \\
\hline 1 & 2 & 1 & 1 & 2 \\
\hline 2 & 2 & 1 & 1 & 2 \\
\hline
\end{array}
$$

So the only case where $(a^2 + b^2) \mod 3 = 0$ is when the LHS modulo pair is (0, 0), i.e. both a and b are multiples of 3, say $a = 3A, b = 3B$ for some non-zero integers $A, B$ (since question states a, b, c are all non-zero). Using this in the original expression, we get $a^2 + b^2 = 9A^2 + 9B^2 = 3 c^2 \Rightarrow A^2 + B^2 = \frac {c^2} {3}$

Since $A^2 + B^2$ and hence $\frac {c^2} {3}$ is an integer, and $c$ is an integer and 3 is prime, it must be the case that $c$ too is a multiple of 3, say $c = 3C$ for some non-zero integer $C$. So the above equivalence becomes, $A^2 + B^2 = \frac {9C^2} {3} = 3C^2$, which is of the same for as the original equation. So as long as the 2 integers on LHS are multiples of 3, we can reduce the expression to another expression of the same form but with the absolute values of the integers becoming smaller. This cannot continue infinitely, implying that we will reach a point where at least one of the 2 integers is no longer a multiple of 3, meaning that the modulo pair is no longer (0, 0). And for any such non-(0, 0) pair, we already showed that the RHS cannot be a multiple of 3, but this contradicts the expression from that required the RHS to be a multiple of 3. Therefore, the only remaining possibility, i.e. of having an LHS module pair of the form (0, 0) that also satisfies the expression form $a^2 + b^2 = 3 c^2$, too is ruled out. Hence proved.

Looks correct. A solution anaologuous to yours was already provided though.

 

[Math_QED]

If $\Sigma _T \cup \Sigma _{S\cap T^c}$ was a finite set, then their generated sub sigma algebra, which is $\Sigma _S$, would also be finite.

I still don't see how (E) implies that

$$\Sigma_S = \sigma(\Sigma_T \cup \Sigma_{S\cap T^c})$$

 

[nuuskur]

I still don't see how (E) implies that

$$\Sigma_S = \sigma(\Sigma_T \cup \Sigma_{S\cap T^c})$$

Right, I wrote $(E)$ for $S=X$ and $T=S$. Perhaps, "similarly to (E)" would have been a better choice of words. The proof is the same up to labelling, regardless. Since $\Sigma _T \cup \Sigma _{S\cap T^c} \subseteq \Sigma _S$ we have
$$\sigma \left (\Sigma _T \cup \Sigma _{S\cap T^c}\right ) \subseteq \Sigma _S.$$
Conversely, for every $A\in\Sigma_S$, we have
$$A = A \cap (T\cup S\cap T^c) = [A\cap T] \cup [A\cap (S\cap T^c)]\in \sigma \left (\Sigma _T \cup \Sigma _{S\cap T^c}\right )$$

 

[Not anonymous]

8. Show that there is no triple $(a,b,c) \in \mathbb{Z}^3\setminus \{(0,0,0)\}$ such that $a^2 + b^2 = 3 c^2$.

After spending a few seconds thinking about it, I realized that this problem is much simpler than what I had imagined when I first came across this question in the challenge list. An interesting problem nevertheless for people like me who have never had the opportunity to a course in number theory and the like and want some warm-up questions before moving to tougher problems.

I think there might be a simpler proof than what I came up with.

Spoiler: A solution for question 8

Since $a^2 + b^2 = 3 c^2$, it must be the case that $a^2 + b^2 \equiv 0 \mod 3$. Since $(x + y) \mod n = x \mod n + y \mod n)$, we consider all possible combinations of $a \mod 3$ and $b \mod 3$ and find their effect on $a^2 \mod 3 + b^2 \mod 3$. We only need to consider the modulo pairs (0, 0), (0, 1), (0, 2), (1, 1), (1, 2) and (2, 2) for the modulos of a and b, since the remaining cases like (2, 1) are symmetric. And we use the observation that if $x \equiv k \mod n$, then $x^2 \equiv k^2 \mod n$ (since $x = pn + k$ for some integer $p$ and $x^2 = (p^2 n^2 + k^2 + 2kpn) \equiv k^2 \mod n$).

$$
\begin{array}{|c|c|c|c|c|}
\hline a \mod 3 & b \mod 3 & a^2 \mod 3 & b^2 \mod 3 & (a^2 + b^2) \mod 3 \\
\hline 0 & 0 & 0 & 0 & 0 \\
\hline 0 & 1 & 0 & 1 & 1 \\
\hline 0 & 2 & 0 & 1 & 1 \\
\hline 1 & 1 & 1 & 1 & 2 \\
\hline 1 & 2 & 1 & 1 & 2 \\
\hline 2 & 2 & 1 & 1 & 2 \\
\hline
\end{array}
$$

So the only case where $(a^2 + b^2) \mod 3 = 0$ is when the LHS modulo pair is (0, 0), i.e. both a and b are multiples of 3, say $a = 3A, b = 3B$ for some non-zero integers $A, B$ (since question states a, b, c are all non-zero). Using this in the original expression, we get $a^2 + b^2 = 9A^2 + 9B^2 = 3 c^2 \Rightarrow A^2 + B^2 = \frac {c^2} {3}$

Since $A^2 + B^2$ and hence $\frac {c^2} {3}$ is an integer, and $c$ is an integer and 3 is prime, it must be the case that $c$ too is a multiple of 3, say $c = 3C$ for some non-zero integer $C$. So the above equivalence becomes, $A^2 + B^2 = \frac {9C^2} {3} = 3C^2$, which is of the same for as the original equation. So as long as the 2 integers on LHS are multiples of 3, we can reduce the expression to another expression of the same form but with the absolute values of the integers becoming smaller. This cannot continue infinitely, implying that we will reach a point where at least one of the 2 integers is no longer a multiple of 3, meaning that the modulo pair is no longer (0, 0). And for any such non-(0, 0) pair, we already showed that the RHS cannot be a multiple of 3, but this contradicts the expression from that required the RHS to be a multiple of 3. Therefore, the only remaining possibility, i.e. of having an LHS module pair of the form (0, 0) that also satisfies the expression form $a^2 + b^2 = 3 c^2$, too is ruled out. Hence proved.

For the last step of my proof, I found a simpler variant, based on same fundamentals however.

Spoiler

We need to prove that $a^2 + b^2 = 3 c^2$ where $(a,b,c) \in \mathbb{Z}^3\setminus \{(0,0,0)\}$ does not have a solution for the case of $(a \mod 3, b \mod 3) \equiv (0, 0)$ (absence of solution for other modulo combinations was already proven).

Say $a = 3^{p}z, b = 3^{q}y, c = 3^{r}z$, where $p, q, r$ are the highest powers associated with 3 in the prime factorization of $a, b, c$ respectively. By this definition, $x, y, z$ will all be non-multiples of 3, implying $x \mod 3 \neq 0, y \mod 3 \neq 0, z \mod 3 \neq 0$. If we assume $(a \mod 3, b \mod 3) \equiv (0, 0)$, then $p, q$ should be positive integers. Therefore, $a^2 + b^2 = 3 c^2 \Rightarrow 3^{2p}x^2 + 3^{2q}y^2 = 3 \times 3^{2r}z^2$. If we arbitrarily assume that $p \ge q$, then LHS becomes $3^{2p} (x^2 + 3^{2q - 2p}y^2)$. The proof of $p \ge q$ case is symmetric.

Subcase 1: If $p = q$, then LHS simplifies further to $3^{2p} (x^2 + y^2)$. Since x, y are non-multiples of 3, $(x^2 + y^2) \mod 3 \neq 0$ as already show earlier, so the exponent of 3 in prime factorization of LHS is $2p$, an even natural number.

Subcase 2: If $p \neq q$, then too exponent of 3 in prime factorization of LHS still remains $2p$, because then in $(x^2 + 3^{2q - 2p}y^2)$, the 2nd component, $3^{2q - 2p}y^2$ would be a multiple of 3 but $x^2$ would not be (because x is not a multiple of 3 by definition), and hence $(x^2 + 3^{2q - 2p}y^2) \mod 3 \neq 0$. So here too, the exponent of 3 in prime factorization of LHS is an even natural number.

Whereas, on the RHS we have $3 \times 3^{2r}z^2 = 3^{2r+1} z^2$, and by definition $z$ is a non-multiple of 3. Hence the exponent of 3 in prime factorization of RHS is $(2r + 1)$, an odd number.

This means that the exponents of 3 on LHS and RHS cannot match, which contradicts the requirement of LHS = RHS. Hence proved

 

[nuuskur]

For the sake of convenience I have put all candidate solutions to this post. If possible, please delete #73 and #76.

The fundamental theorem of abelian groups says that for any finite abelian group
$$
A \cong \mathbb Z_{p_1^{k_1}} \oplus \ldots \oplus \mathbb Z_{p_m^{k_m}}
$$
I'll be using Sylow's theorems which I will refer to as theorems 1, 2 and 3 respectively. (https://en.wikipedia.org/wiki/Sylow_theorems)

Spoiler: Result

Of order $6$ there are
$$
\mathbb Z_6 \qquad S_3.
$$
Of order $8$ there are
$$
\mathbb Z_8 \qquad \mathbb Z_4 \oplus \mathbb Z _2 \qquad \mathbb Z_2 \oplus\mathbb Z_2\oplus\mathbb Z_2\qquad D_4 \qquad \mbox{Dic}_2.
$$
Of order $12$ there are
$$
\mathbb Z_{12}\qquad \mathbb Z_6 \oplus \mathbb Z_2 \qquad A_4 \qquad \mathbb Z_3 \rtimes_\varphi \mathbb Z_4 \qquad \mathbb Z_3 \rtimes _\varphi (\mathbb Z_2\oplus\mathbb Z_2).
$$

Spoiler: Problem 5 - order 6

In the abelian case there are $\mathbb Z_6\cong\mathbb Z_2\oplus\mathbb Z_3$.

Quick remark. Being a Sylow $p-$subgroup is invariant with respect to conjugating, thus if $H$ was a unique Sylow $p-$subgroup, we would have$gHg^{-1} = H, g\in G,$ i.e $H$ would be normal.

Fact. Suppose a non-abelian group $G$ has order $pq$ (primes) with $q\equiv 1 \pmod{p}$, then there are precisely $q$ Sylow$p-$subgroups in $G$.

Proof of fact. Let $n_p,n_q$ be the numbers of Sylow $p,q-$subgroups respectively. By assumption $q>p$. By theorem 3 $n_q \equiv 1 \pmod{q}$ and $n_q\mid p$, which forces $n_q = 1$, thus we have a (normal) subgroup of order $q$, which makes it cyclic, therefore abelian.

For $n_p$ we thus have two choices: $n_p = 1,q$. If $n_p = 1$, then $G\cong \mathbb Z_p \oplus \mathbb Z_q$ would be abelian, thus it must be that $n_p = q$.

Our non-abelian group $G$ therefore contains three Sylow $2-$subgroups, call them $H_1,H_2,H_3$, which by theorem 2 are all conjugate to each other. We have $\mbox{Sym}(H_1,H_2,H_3) \cong S_3$. We show that $G\cong S_3$. Define
$$\varphi : G\to \mbox{Sym}(H_1,H_2,H_3), \quad\varphi (g)(H_j) := gH_jg^{-1}$$
(also called conjugating)

Spoiler: well-defined, morphism

Firstly, if $H$ is a Sylow $p-$subgroup, then conjugating it gives another Sylow $p-$subgroup, hence it must hold that $gH_ig^{-1} = H_j$ for some $j$.

The map $\varphi (g)$ is injective, because if $gH_ig^{-1} = gH_jg^{-1}$, then
$$h_i \in H_i \Rightarrow gh_ig^{-1} \in gH_ig^{-1} = gH_jg^{-1} \Rightarrow h_i \in H_j.$$
The argument is symmetrical, thus $H_i=H_j$. It is surjective due to finiteness.

Take $g,h\in G$, then
$$\varphi (gh) (H_j) = (gh)H_j(gh)^{-1} = g(hH_jh^{-1})g^{-1} = g (\varphi (h)(H_j)) g^{-1} = \varphi (g) (\varphi (h)(H_j)) = (\varphi (g) \varphi (h))(H_j).$$

To show it's an isomorphism, it suffices to show it's injective (because $|G| = |S_3| = 6$). Suppose $\varphi (g) = \mbox{id}$ i.e $gH_jg^{-1}=H_j$, then by definition $g\in N(H_j)$ the normaliser of $H_j$. By theorem 3 all $N(H_j) = H_j$ and $g\in H_1\cap H_2\cap H_3 = \{e\}$ i.e $g=e$, which makes $\varphi$ an isomorphism.

Spoiler: Problem 5 - order 8

In the abelian case there are
$$\mathbb Z_8 \qquad \mathbb Z_4 \oplus \mathbb Z _2 \qquad \mathbb Z_2 \oplus\mathbb Z_2\oplus\mathbb Z_2$$
Suppose $G$ is non-abelian of order $8$. If there is an element of order 8, then $G$ is cyclic, thus abelian. Suppose the maximal order is $2$ and pick $g,h\in G$. If $gh=e$, then they commute. Suppose $(gh)^2 = e$, then
$$gh = geh = g(ghgh)h = (gg)hg(hh) = ehge = hg$$
and again $G$ would be abelian. Thus we must have an element $a$ of order $4$. Its generated subgroup $\langle a \rangle =: H$ is of index $2$, therefore normal. Take $b\notin H$, then we have $bab^{-1}\in H$ due to normality. Notice that
$$(bab^{-1})^4 = bab^{-1}bab^{-1}bab^{-1}bab^{-1} = baaaab^{-1} = e.$$
If also $(bab^{-1}) ^2 = e$, then $baab^{-1} = e$ would lead to $aa=e$, contradicting the order of $a$.
Next, we find the possible values of $bab^{-1}$.

1. If $bab^{-1} = a^4 = e$, then $a=e$, which is impossible.
2. If $bab^{-1} = a$, then $ba = ab$, but this will make $G$ abelian. Indeed, pick $g,h\in G$. If they're both in $H$, then they commute. Suppose $g\notin H$ and write $g = ba^m$ and $h = a^n$, then
   $$gh = ba^ma^n = ba^na^m = a^n ba^m = hg.$$
   and if both reside outside $H$, then writing $g = ba^m$ and $h = ba^n$ would similarly lead to $gh=hg$. But our group is not abelian.
3. If $bab^{-1} = a^2$, then $(bab^{-1})^2 = e$ would contradict the order of $bab^{-1}$.

Thus, the only possibility is $bab^{-1}=a^3 =a^{-1}$.

There are two cases to consider.

1. $b$ is of order $2$, then we have $G \cong \langle a,b \mid \mbox{ord}(a) = 4, \mbox{ord}(b) = 2, bab^{-1} = a^{-1} \rangle$ this is the dihedral group $D_4$.
2. $b$ is of order $4$. We show $G$ is the dicyclic group $\mbox{Dic}_2$, where
   $$\mbox{Dic}_2 \cong \langle x,y \mid x^{4} = e, x^2 = y^2, x^{-1} = y^{-1}xy \rangle.$$
   Notice that
   $$bab^{-1} = a^{-1} \Rightarrow b^{-1}ab = b^{-1}(ba^{-1}b^{-1})b = a^{-1}.$$
   So we have left to show $a^2 = b^2$. Considering the natural projection $G\to G/H\cong\mathbb Z_2$, we have $b^2 \in H$. Consider possible values of $b^2$.
   1. $b^2 = a^4 = e$ contradicts order of $b$.
   2. $b^2 = a$ contradicts order of $a$
   3. $b^2 = a^2$ is what we want.
   4. $b^2 = a^{-1}$ contradicts order of $a^{-1}$ (hence order of $a$).
      Thus $b^2 = a^2$ must hold.

Spoiler: Problem 5 - order 12

In the abelian case there are
$$\mathbb Z_{12}\qquad \mathbb Z_6 \oplus \mathbb Z_2.$$

Suppose $G$ is non-abelian of order 12. Let $H_p$ denote a Sylow $p-$subgroup and $n_p$ the number of Sylow $p-$subgroups in $G$. Then, by theorem 1, we consider subgroups $H_2$ and $H_3$. The case $n_2=n_3=1$ yields normality and $H_2 \cong \mathbb Z_4$ or $H_2 \cong \mathbb Z_2\oplus \mathbb Z_2$ and $H_3 \cong \mathbb Z_3$ and that leads to one of the previously mentioned abelian structures.

Case 2 : $n_3= 4$. Call them $H^1,H^2,H^3,H^4$. Define
$$\varphi : G \to \mbox{Sym}(H^1,H^2,H^3,H^4) \cong S_4, \quad \varphi (g) := gH^jg^{-1}.$$
Since conjugation preserves the property of being a Sylow $p-$subgroup and injectivity of each $\varphi (g)$ is trivial, the map is well-defined. It's a routine task to check it's a morphism.

Notice, if, say, $aH^ia^{-1} = H^j$, then $aN(H^{i})a^{-1} = N(H^j)$, so taking normalisers preserves the property of being conjugate.

Now, suppose $\varphi (g) = \mbox{id}$, then by definition $g\in N(H^j)$. By theorem 3 $N(H^j) = H^j$, thus $g=e$ is forced and $\varphi$ is injective. Furthermore, each $H^j$ contains two generators, therefore $G$ has $8$ elements of order 3.

Consider the alternating group $A_4$. Trivially $\varphi (G) \cap A_4 \leqslant\varphi (G)$ and $A_4$ also contains $8$ elements of order 3, thus $G\cong A_4$.

Case 3: $n_3 = 1$. Call it $H$ and pick a Sylow $2-$subgroup $K$ (of order $4$). As $H$ is normal it holds $HK$ is a subgroup of $G$. As $H\cap K = \{e\}$ (by orders of elements), then
$$|HK| = \frac{|H||K|}{|H\cap K|} \Rightarrow HK = G.$$
We show $G\cong H\rtimes _\varphi K$, the semidirect product under $\varphi : K\to \mbox{Aut}(H)$, where
$$(h,k)\cdot (h',k') := (h\varphi (k)(h'),kk')$$
This will yield two more groups, namely the following:
$$\mathbb Z_3 \rtimes_\varphi \mathbb Z_4 \qquad \mathbb Z_3 \rtimes _\varphi (\mathbb Z_2\oplus\mathbb Z_2).$$
Define
$$\varphi : K\to \mbox{Aut}(H),\quad \varphi (k)(h) := khk^{-1}.$$
I will omit the routine checks. We show
$$\tau : G\to H\rtimes _\varphi K, \quad g=hk \mapsto (h,k),$$
is an isomorphism. Although, let's have some fun and do it the category theory way, for a change. First, we check $\tau$ is a morphism. Take $g=hk, g'=h'k'\in G$, then due to normality $kh'k^{-1} \in H$ and we get
$$\begin{align*} \tau (hkh'k') &= \tau (h(kh'k^{-1})kk') \\ &= (h(kh'k^{-1}),kk')\\ &= (h\varphi (k)(h'),kk')\\ &= (h,k)(h',k')\\ &= \tau (hk) \tau (h'k'). \end{align*}$$
Also $\tau (e) = \tau (ee) = (e,e)$. Now define
$$\omega : H\rtimes _\varphi K \to G, \quad (h,k) \mapsto hk.$$
Verify it, too, is a morphism. Take $(h,k),(h',k')\in H\rtimes _\varphi K$, then
$$\begin{align*} \omega ((h,k)(h',k')) &= \omega ((h\varphi (k)(h'), kk'))\\ &= h(kh'k^{-1})kk' \\ &= hkh'k' \\ &= \omega ((h,k)) \omega ((h',k')). \end{align*}$$
Also $\omega ((e,e)) = ee = e$. The equalities $\tau\omega = \mbox{id}_{H\rtimes _\varphi K}$ and $\omega\tau = \mbox{id}_G$ are straightforward to verify.

 

[Math_QED]

Right, I wrote $(E)$ for $S=X$ and $T=S$. Perhaps, "similarly to (E)" would have been a better choice of words. The proof is the same up to labelling, regardless. Since $\Sigma _T \cup \Sigma _{S\cap T^c} \subseteq \Sigma _S$ we have
$$\sigma \left (\Sigma _T \cup \Sigma _{S\cap T^c}\right ) \subseteq \Sigma _S.$$
Conversely, for every $A\in\Sigma_S$, we have
$$A = A \cap (T\cup S\cap T^c) = [A\cap T] \cup [A\cap (S\cap T^c)]\in \sigma \left (\Sigma _T \cup \Sigma _{S\cap T^c}\right )$$

I went through your solution again and I think it is correct! Well done!