Find the element with the greatest order in the group $(\mathbb Z/2^{100}\mathbb Z)^*$. (Probably Lagrange theorem) Find the element with the greatest order in the group $(\mathbb Z/2^{100}\mathbb Z)^*$.
We know that $k$ divides $|G|$ (where $k$ is the order of any subgroup). Let's find $|G|$. We need to exclude all even numbers, so it's $2^{99}$. Ok, $k$ is a power of $2$. Let's run some code, and get that $k$ is very probably $2^{98}$. It means that there are only 2 cycles here.
What to do next?
 A: From the Carmichael function, it follows that the maximum order of all elements of $(\mathbb{Z}/2^{n}\mathbb{Z})^\times$ for $n\geq 3$ is $2^{n-2}$.
As for finding an element that satisfies this property, it is pretty easy to pick something like $2^{97}-1$ and then use binomial theorem. There are of course plenty of other examples, and binomial expansion will be useful to finding those.
A: We can simply observe, using the binomial theorem, that
$$
3^{2^{98}}=(1+2)^{2^{98}}\equiv1\pmod{2^{100}},
$$
и
$$
3^{2^{97}}=(1+2)^{2^{97}}\equiv1+2^{99}\pmod{2^{100}}.
$$
This means that 3 has order $2^{98}$ in the group $\mathbb{Z}_{2^{100}}$.
Since the order of the group $G=\mathbb{Z}_{2^n}$ is $2^{n-1}$ and this group at $n\geq3$ has a noncyclic subgroup of order 4
$$
H=\{1,-1,2^{n-1}-1,2^{n-1}+1\},
$$
it follows that the order of elements in the group $G$ is at most $2^{n-2}$.
A: You could apply some theory like :

*

*If $a$ has odd order it's additive inverse $-a$ has double that order. If even order, either same or half the order .

*since $1$ is it's own multiplicative inverse, and multiplicative inverses raised to any power are multiplicative inverses, the multiplicative inverse of $a$ , has same order as $a$

*The additive inverses, of multiplicative inverses, are multiplicative inverses.

*Order of powers are always no more than order of the bases. If exponent has a GCD greater than 1 with the order of the base, then it has a smaller order.

*The order of a product is the LCM of the order of it's multiplicands.

To narrow choices a bit (mostly to primes).
