Tagged Questions
3
votes
3answers
74 views
Sum of two squares in a $\Bbb Z/p\Bbb Z$
I need to show that every element in $\Bbb Z/p\Bbb Z$ can be written as a sum of two squares. The case $p=2$ is trivial and $0$ is always $0^2 + 0^2$. So all I have to do is show that every element of ...
2
votes
0answers
48 views
Element of a certain order in multiplicative group of residues
Let's say that $G$ is the multiplicative group of residues mod $p$, where $p$ is prime. I know that the order of an element $g \in G$ is the least $k$ for which $g^k \equiv 1 \mod{p}$.
How can we go ...
3
votes
3answers
138 views
Why multiplicative group $\mathbb{Z}_n^*$ is not cyclic for $n = 2^k$ and $k \ge 3$
Let G be the multiplicative group $\mathbb{Z}_n^*$ for $n = 2^k$ and $k \ge 3$.
Can we prove that no element has order bigger than $2^{k-2}$ ?
My solution (not really a solution) :
Since $n=2^k$, I ...
12
votes
3answers
163 views
What is the order of $2$ in $(\mathbb{Z}/n\mathbb{Z})^\times$?
Is it there some theorem that makes a statement about the order of $2$ in the multiplicative group of integers modulo $n$ for general $n>2$?
6
votes
1answer
188 views
Which families of groups have interesting formulas for the number of elements of given order?
Suppose that $G$ is a group and that $n$ is a positive integer diving the order of $G$. Let $f_n(G)$ be the number of elements satisfying $x^n = 1$ in $G$. According to a theorem of Frobenius, then we ...
2
votes
2answers
93 views
Why is the order of an element in the group of units mod n , $U(n)$, equal to the totient of n?
I came across this statement in an abstract algebra textbook, I am looking for a proof.
EDIT: I guess I was not clear, what I meant was
If $k\ \epsilon\ U(n)$ and $m\ \epsilon\ \mathbb{Z}^+$ and
...
0
votes
4answers
75 views
$(p,\frac{n}{p^\alpha})=1$ then $p\nmid\binom{n}{p^\alpha}$
Let $n=p^\alpha m$ wherein $(p,m)=1$. Then we have $$p\nmid\binom{n}{p^\alpha}$$ What I have done is just playing with $\binom{n}{p^\alpha}$ ...
3
votes
1answer
64 views
Why are generators of $Z^{*}_p, p=c \cdot 2^k + 1$ so small?
I was implementing NTT for long integer multiplication and thus searched for generators of several $Z^{*}_p$ groups where $p=c\cdot 2^k + 1$.
I used the algorithm described in Wikipedia which uses ...
3
votes
1answer
169 views
Primitive root modulo $p$
I am currently trying to find a primitive element of the multiplicative group of field $GF(p)$. Since the numbers are relatively small, I know the factorization of
$$\phi(p)=p-1 = {p_1}^{k_1} ...
3
votes
0answers
123 views
A subclass of metacyclic groups
A group $G$ is metacyclic if it contains a cyclic normal subgroup $N$, such that $G/N$ is also cyclic. $N$ is called the kernel, and the order of $G/N$ is the index of the metacyclic group. There is ...
