# Tour:Hard nuts four (beginners)

PREVIOUS: Mind's eye test four (beginners)| UP: Introduction four | NEXT: Interdisciplinary problems four (beginners)
NEXT SECTION Hard nuts: Hard nuts five
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

This includes problems that are either too hard or too unimportant to be part of the mind's eye test. Learners are not required to tackle these problems, and can skip ahead without loss of continuity. These problems are ideal for people revisiting the tour or seeking a challenge.

1. NEEDS LOT OF THOUGHT: Suppose $H,K,L$ are subgroups of $\mathbb{Z}$. Prove (by reducing the problem to one involving lcm and gcd, and then using the definitions of lcm and gcd in terms of prime factorization) that:
• $\langle H, K \cap L \rangle = \langle H, K \rangle \cap \langle H, L \rangle$
• $H \cap \langle K, L \rangle = \langle H \cap K, H \cap L\rangle$
2. NEEDS SOME THOUGHT: Prove the results above, replacing $\mathbb{Z}$ by any cyclic group.
3. NEEDS SOME THOUGHT: Let $A$ be a finite subset of $\mathbb{Q}$. Prove that the subgroup generated by $A$ is cyclic. (A group with the property that every finite subset generates a cyclic group is termed a locally cyclic group).
4. NEEDS SOME THOUGHT: Suppose $(G,+)$ is an Abelian group and $g \in G$, such that there exist $a,b \in G$, such that $2a = 3b = g$. Prove that there exists a $c \in G$ such that $6c = g$. Generalize the result replacing 2,3 by any two integers, and replacing 6 by the least common multiple of these integers.
5. Using the previous problem, prove that if an arithmetic progression of integers contains a perfect square and a perfect cube, then it contains a perfect sixth power. (Hint: First use the previous problem to solve the case where the common difference is relatively prime to the terms of the progression)
6. Prove that the multiplicative group of all roots of unity in $\mathbb{C}$ is locally cyclic: the subgroup generated by any finite subset is cyclic.
7. NEEDS LOT OF THOUGHT: Prove that any additive subgroup of $\R$ is either dense or infinite cyclic, generated by the positive element of smallest magnitude in it. (Dense here means that it intersects every open interval, and cyclic means that it is additively generated by an element). This is a generalization of the fact that any subgroup of $\mathbb{Z}$ is infinite cyclic.
8. NEEDS LOT OF THOUGHT: Prove that if a finite group of order $n$ has exactly one subgroup of order $d$ for each $d|n$, then the finite group is cyclic. (Hint: Use the general result obtained in the Mind's eye test, about any finite group equal to the union of the set of generators for its cyclic subgroups)

## Multiplicative groups

For these exercises, use the fact that if $p$ is prime, the multiplicative group mod $p$ is a cyclic group. Direct application of Fermat's little theorem, and the concept of order of an element, are useful.

1. An element $a$ mod $p$ (not zero mod $p$) is termed a quadratic residue mod $p$ if there exists $x$ such that $x^2 \equiv a \mod p$. Otherwise $a$ is termed a quadratic nonresidue. Prove that for an odd prime $p$, there are exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. Further, show that $a$ is a quadratic residue mod $p$ if and only $a^{(p-1)/2} \equiv 1 \mod p$, and $a$ is a quadratic nonresiude if and only if $a^{(p-1)/2} \equiv -1 \mod p$.
2. Prove that the quadratic residues form a subgroup of index two, and the quadratic nonresidues form the other coset.
3. A primitive element mod $p$ is an element that generates the multiplicative group mod $p$. Prove that there are exactly $\varphi(p - 1)$ primitive elements.
4. The $n^{th}$ Fermat number is defined as: $F_n = 2^{2^n} + 1$. Prove that if $p$ is a prime divisor of $F_n$, then $p-1$ is a multiple of $2^{n+1}$.
5. An element $a$ mod $p$ (not zero mod $p$) is termed a cubic residue mod $p$ if there exists $x$ such that $x^3 \equiv a \mod p$. Prove that the cubic residues form a multiplicative subgroup of the multiplicative group mod $p$. Further prove that if $3 | p -1$, then this subgroup has index three, and otherwise, the subgroup is the whole group.
6. Prove that if $q$ is a prime divisor of $a^p - 1$ for a prime $p$ and an integer $a > 1$, then either $p | q - 1$ or $q | a - 1$.