1
vote
1answer
30 views

Understanding the elements in groups(modulo, cyclic and other(?))

Question exactly as given on past exam: Consider the group $G=(\mathbb{Z}/15\mathbb{Z})^\times$ (under multiplication). Let $H$ be the subgroup generated by $2$ (that is, $H = \langle 2 \rangle$). ...
3
votes
2answers
97 views

Is there any usage of this sum formula?

Let $\phi$ be the Euler phi function, then $$n=\sum_{d|n}\phi(d)$$ It is one of the most famous formulas in number theory. It can be generalized by using groups. Let $G$ be a group of order $n$ and ...
1
vote
0answers
40 views

Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F} $

Is there a map between the group of $\mathbb{Z}_{N^2}^*$ where $N$ is a composite number , a product of two equal size secure prime numbers $p$ and $q$ and a finite field $\mathbb{F}$, such that for ...
0
votes
0answers
53 views

Show that the number of elements in the equivalence class is n?

Question is : Let $G$ be a finiote group of order n = $p^{\alpha}$m, where $p$ is a prime number and if $p^r$ | m but $p^{r+1} \nmid$ m Let $\mathcal M$ be the set of all subset of $G$ which have ...
2
votes
2answers
73 views

Fast way of calculating the order of an element in $\mathbb{Z}_n$?

Is there a fast way of calculating the order of an element in $\mathbb{Z}_n$? If i'm asked to calculate the order of $12 \in \mathbb{Z}_{22}$ I just sit there adding $12$ to itself and seeing if the ...
1
vote
1answer
35 views

Solving for $x$ where $p^x \equiv 1 \pmod {q\#}$

For a given primorial $q\#$, you can generate a subset of the reduced residue system by using the power of a prime $p$ where $p > q$. For example, for $5\#$, we can use the powers of $7$ to ...
1
vote
1answer
60 views

Let $\tau_1, \tau_2 \in A_6$ be permutations with cycle-type $(2, 4)$. Show there exists $\tau \in A_6: \tau \tau_1 \tau^{-1} = \tau_2.$

Let $\tau_1, \tau_2 \in A_6$ be permutations with cycle-type $(2, 4)$. Show there exists $$\tau \in A_6\mid \tau \tau_1 \tau^{-1} = \tau_2$$ I know $\tau_1 = (a b c d)(e f)$ and $\tau_2 = ...
4
votes
2answers
68 views

How to prove that $a^{2^{n-2}} \equiv 1 \pmod{2^n}$?

Let $a$ be an odd integer and $n$ an integer such that $n\ge 3$. 1) I want to show that $a^{2^{n-2}} \equiv 1 \pmod{2^n}$ 2) Then I want to show that $(\mathbb Z/{2^n\mathbb Z})^*$, the ...
2
votes
1answer
73 views

Are algebraic properties consistent among ALL types of number groups?

I'm embarking on a self study course of group theory, modular arithmetic, and other mathematics relating to cryptography. I notice that when studying modular arithmetic that they explicitly say that ...
1
vote
1answer
134 views

Show that $HK=\mathbb{Z}_n^\times$

Let $p$ and $q$ be distinct prime numbers and $n=pq$. Show that $HK=\mathbb{Z}_n^\times$ for the subgroups $H=\{[x]\in\mathbb{Z}_n^\times\mid x\equiv 1\pmod{p}\}$ and $K=\{[y]\in\mathbb Z_n^\times ...
2
votes
1answer
74 views

Counting the subgroups of $\Bbb Z_4 \times \Bbb Z_6 \times \Bbb Z_9$ of index 3

I'm trying to solve the following problem from a past exam. Find the number of the subgroups of $P:=\Bbb Z_4 \times \Bbb Z_6 \times \Bbb Z_9$ of index 3. Here $\Bbb Z_m$ denotes $\Bbb Z/m\Bbb ...
1
vote
1answer
68 views

Generator of all congruence classes

Is it possible for $\langle a \rangle =\mathbb Z/n\mathbb Z^*$ for $a\in \mathbb Z/n\mathbb Z^*$? I think I recall hearing it is, what is the name this element takes? I remember hearing generator ...
3
votes
1answer
97 views

The structure of $(\mathbb Z/525\mathbb Z)^\times$

I am working on the following problem. Find the number of the elements of order 4 in $(\mathbb Z/525\mathbb Z)^\times$. I tried to solve it in the following way: since $525=3\cdot5^2\cdot7$, we ...
0
votes
1answer
65 views

Diophantine equation and cyclicity of $\mathbb{F}_p^*$

I am trying to prove that the diophantine equation $$1998^2x^2+1997x+1995-1998x^{1998}=1998y^4+1993y^3-1991y^{1998}-2001y$$ has no solution in integers (given that $1997$ is a prime). To do so, ...
1
vote
0answers
50 views

How to build $\operatorname{Hom}(\mathbb{Z}_p^*,\mathbb{Z}_{pq}^*)$ without solving DLP?

For given two distinct primes p and q, I want to construct all homomorphisms from the multiplicative group $\mathbb{Z}_p^*$ to the multiplicative group $\mathbb{Z}_{pq}^*$. Thanks to Jyrki ...
1
vote
1answer
83 views

Is there other homomorphisms from $\mathbb{Z}_q^*$ to $\mathbb{Z}_{pq}^*$?

For given two distinct primes p and q, is there other homomorphisms from the multiplicative group $\mathbb{Z}_q^*$ to the multiplicative group $\mathbb{Z}_{pq}^*$, except the following two maps: ...
1
vote
1answer
102 views

Is there non-trivial homomorphism from $\mathbb{Z}_q^*$ to $\mathbb{Z}_p^*$?

For two distinct primes $q$ and $p$, is there non-trivial homomorphism from $\mathbb{Z}_q^*$ to $\mathbb{Z}_p^*$? Here, $\mathbb{Z}_q^*$ and $\mathbb{Z}_p^*$ mean the multiplication groups with ...
2
votes
2answers
110 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 ...
1
vote
1answer
266 views

Computing $\bmod$s with large exponents by paper and pencil using Fermat's Little Theorem.

I'm having a bit of trouble computing $\bmod{mod}$s of large numbers using Fermat's Little Theorem. For example, how would you compute $7^{435627650}\mod 13$? The solution given is $435627650\mod ...
2
votes
0answers
119 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 ...
4
votes
3answers
329 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
182 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$?
9
votes
1answer
513 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
198 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 ...
1
vote
4answers
83 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
73 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 ...
4
votes
1answer
216 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
165 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 ...