1
vote
2answers
49 views

Non cyclic subgroup of $\mathbb{Z}_5$

Let $H = \{0, 2, 3\} \subset \mathbb{Z}_5$. $H$ is a subgroup of $\mathbb{Z}_5$, since it is closed with respect to addition and with respect to inverses. Given that $\langle 2 \rangle = ...
0
votes
2answers
56 views

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$? I have made several observations about the problem but I cant see how they lead me to an answer. Observation one: ...
3
votes
1answer
30 views

Group of numbers in residue number system of first $n$ primes

Denote $$\Pi_n = \Pi_{i=1}^n p_i$$ ie. the product of the first $n$ primes. Assume we have a number $m$. Denote $$L(m) = k \iff \Pi_{k-1} < m \le \Pi_{k}.$$ Assume also $L(1)=1.$ Now, if $L(m) = ...
1
vote
3answers
63 views

Calculating $x^{103} \equiv 2 \pmod{143}$

I need to find x, given that: $0\leq x \leq 143$ and $x^{103}\equiv 2 \pmod{143}$. I tried to use Euler's theorem $p(143)=120$, but it didn't help.
0
votes
1answer
33 views

Why is $U(12) = U_{4} (12) ~ U_3(12)?$

Why is $U(12) = U_{4} (2)~ U_3(12)$ Attempt: Any subgroup $U_k(n) = \{x \in U(n)~~|~~x \mod k=1 , k ~|~n \}$ Hence : if $U(12) =\{1,5,7,11\}$ then : $U_4(12) =\{1,5\}$ and $U_3(12)=\{1,7\}$ We see ...
1
vote
1answer
40 views

$|p+1|=p^{n-1}$ in $\left( \mathbb{Z}/p^n \mathbb{Z} \right)^\times$

I want to solve the following exercise from Dummit & Foote's Abstract Algebra: Let $p$ be an odd prime and let $n$ be a positive integer. Use the Binomial Theorem to show that $(1+p)^{p^{n-1}} ...
3
votes
3answers
42 views

If $n > 2$, prove that the order of the multiplicative group of units modulo n, $U_n$, is even.

I'm struggling with this. I know it is going to use Lagrange's Theorem so this is what I have so far: Suppose $|U_n| = k$ This implies $a^k = 1$ for all a in $U_n$ and $|a|$ divides $k$. Now, what ...
4
votes
0answers
32 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...
1
vote
3answers
47 views

Multiplying modulo 20

For a positive integer $n \ge 2$, define $U(n)= \{k \in \Bbb Z_n $| gcd$(k,n)=1\}$. Then $U(n)$ is a group under multiplication modulo $n$. Find the order of $U(20)$. Is it possible to generate ...
0
votes
1answer
16 views

Modular Group Arithmetic with Primes

I need help understanding what this means: Working in sets $\mathbf Z_N^* = \{a \in \{0,1,...,N-1\} : gcd(a,N) = 1\}$ If I have a prime $p$ then I claim there is a value $k$ such that $g^x = ...
0
votes
3answers
57 views

How many subgroups there is for $\mathbb{Z}_{23}\times \mathbb{Z}_{31}$?

How many subgroups there is for $\mathbb{Z}_{23}\times \mathbb{Z}_{31}$? I try to understand how to solve it but I don't finding a way... I'll be glad if you help me with this... Thank you!
1
vote
1answer
118 views

Find period of power sequence $a^k \mod m$, with $a, m$ not coprime

Let $a, m$ be positive integers and $m > 1$. I'm interested in the sequence $(a^k)_{k \in \mathbb{N_0}} \mod m$. Since there are only $m$ different values that can occur in the sequence and since ...
0
votes
1answer
53 views

Finding subgroups via modulo arithmetic [closed]

Consider the following numbers : $1, 3, 7, 9, 11, 13, 17, 19$. In terms of modulo $20$ how many subgroups are there? For example, $3(7) = 21 = 1$ mod $20$. In particular I want to find the ...
0
votes
1answer
67 views

A nice group isomorphism

Show that $$k(\mathbb{Z}/n\mathbb{Z})\cong (\gcd(n,k)\mathbb{Z})/n\mathbb{Z}.$$ I want to see as many as possible proofs of this nice fact.
4
votes
2answers
85 views

How do I prove that $a\in (\mathbb{Z}_{p}^{*})^2 \Leftrightarrow a^{\frac{p-1}{2}}\equiv 1 \pmod p$

$p$ is prime number $>2$ and $a$ is a square. $\mathbb{Z}_{p}^{*} $ is a cyclic group. I need to show that $$ a\in (\mathbb{Z}_{p}^{*})^2 \iff a^{\frac{p-1}{2}}\equiv 1 \pmod p $$ Any ideas ...
1
vote
1answer
106 views

Raising a cycle to a power, cycle decomposition

Let $\alpha$ be an m-cycle. Is it true that $\alpha ^k$ can be decomposed into $\gcd(m,k)$ disjoint cycles? for example $(1 2 3 4 5 6)^2 = (1 3 5)(2 4 6)$, $(1 2 3 4 5 6 7 8)^6 =(1 7 5 3)(2 8 6 ...
1
vote
2answers
73 views

Multiplication modulo proving a set is a group conform conditions

Given is the following explanation. A group is a set, together with a binary operation $\odot$, such that the following conditions hold: For all a, b $\in$ S it holds that a $\odot$ b $\in$ S ...
0
votes
1answer
68 views

Question about the order of an element at $\mathbb{Z}_{n}^{*}$

Assume that $n,q>1$ and $n=\frac{q^r-1}{q-1}$. I know that $q\in\mathbb{Z}_{n}^{*}$. How do I prove that $ord(q)=r$? This is the meaning of $\mathbb{Z}_{n}^{*}$: $$\mathbb{Z}_{n}^{*}= ...
1
vote
1answer
34 views

Question about an element at $\mathbb{Z}_{n}^{*}$

Assume that $n,q>1$ and $n=\frac{q^r-1}{q-1}$. How do I prove that $q\in \mathbb{Z}_{n}^{*}$? $$\mathbb{Z}_{n}^{*}= \left\{a\mid1\le a<n;\ \gcd(a,n)=1 \right\}$$ Thank you!
5
votes
4answers
118 views

${{p-1}\choose{j}}\equiv(-1)^j \pmod p$ for prime $p$

Can anyone share a link to proof of this? $${{p-1}\choose{j}}\equiv(-1)^j(\text{mod}\ p)$$ for prime $p$.
1
vote
1answer
44 views

Order of modular group

Prove $|(\mathbb{Z} / p^e \mathbb{Z} )^{\times}| = p^e - p^{e-1}$ I know it has something to do with the fact that we have $p^e$ elements and we're substracting $p^{e-1}$ multiples of $p$, but I'd ...
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 ...
0
votes
3answers
126 views

Why is the group of units mod 8 isomorpic to the Klein 4 group?

I recently learned that $U_8\cong \mathbb Z/2\mathbb Z\oplus \mathbb Z/2\mathbb Z$. I can see, through a bit of computation, that this is the case, but I was wondering if this is just a coincidence ...
0
votes
1answer
121 views

Is a congruence (equivalence) class modulo n a group?

I know that the set of all equivalence classes Z/nZ is a group (with identity element the equivalence class [0], inverse element -[a]=[n-a]=[-a], etc.). However, is a single equivalence class modulo ...
2
votes
1answer
185 views

Subgroups of $U(n)$ isomorphic to a direct sum of cyclic groups

Let $U(n)$ to be the set of all positive integers less then $n$ and relatively prime to $n$. Then $U(n)$ is a group under multiplication modulo $n$. A. Find integer $n$ such that $U(n)$ contains ...
3
votes
1answer
107 views

Natural Representation of Factor Group $G/H$

Let $G$ be the positive reals under multiplication and let $H$ be numbers $2^i$ where $i \in \mathbb{Z}$. a) Show H is a subgroup of G b) Show H is a normal subgroup of G Those two are no problem, ...
8
votes
1answer
89 views

Finding the generators of a subgroup of $\mathrm{SL}_2(\mathbb Z)$

I am trying to solve the following problem: Let $T_{ij}(c)\in\mathrm{SL}_2(\mathbb Z)\ (i\neq j)$ be the elementary matrix which represents the elementary row operation of adding the $j$-th row ...
0
votes
1answer
63 views

How to determine if $G$ contains an element of order $k$?

I'm struggling with this kind of problem: Given a group $G= (\mathbb{Z}/n\mathbb{Z})^*$ (which is the multiplicative modulo group), determine if the group contains an element of order $k$. What is ...
0
votes
2answers
48 views

Looking for an integer for which the $(\mathbb{Z}/n\mathbb{Z})^*$ contains elements with certain orders

I don't need a specific answer or whatever, but I'm looking for a strategy to solve this kind of problems. The specific question I have in mind is: Give an integer $n$ for which the multiplicative ...
1
vote
1answer
142 views

Homomorphism between multiplicative group of integers modulo n

Just looking for anybody to check the following: We have got a homomorphism $f: (\mathbb{Z}/42\mathbb{Z})^{*} \rightarrow (\mathbb{Z}/21\mathbb{Z})^{*}$, given by $f(a\text{ mod} 42)= a \text{ mod} ...
3
votes
1answer
59 views

Primitve roots and congruences?

Let $p$ be an odd prime. Show that the congruence $x^4$$\equiv -1\text{ (mod }p\text{)}\ $ has a solution if and only if $p$ is of the form $8k+1$. Here is what I did Suppose that $x^4$$\equiv ...
-2
votes
1answer
93 views

Finding a primitive root modulo $13$ [duplicate]

Find a primitive root modulo each of the following integers. a) $13$ My TA said we are not going to go over this. We did not go over the topic. It seems like something good to know though. ...
1
vote
1answer
211 views

Finding a primitive root modulo $11^2$

Find a primitive root modulo each of the following moduli: a) $11^2$ My TA said he is not going to go over this so do not worry about it. He said you can try this if you want but he would ...
3
votes
2answers
176 views

$\mathbb Z_p^*$ is a group.

I'm trying to prove that $\mathbb Z_p^*$ ($p$ prime) is a group using the Fermat's little theorem to show that every element is invertible. Thus using the Fermat's little theorem, for each $a\in ...
6
votes
3answers
145 views

Aut $\mathbb Z_p\simeq \mathbb Z_{p-1}$

I'm trying to prove that Aut $\mathbb Z_p\simeq \mathbb Z_{p-1}$ (p prime). I know that Aut $\mathbb Z_p$ has $p-1$ elements because $\mathbb Z_p$ has $p-1$ possiblities of generators, so intuitively ...
0
votes
2answers
60 views

Trying to prove $A=\{2, 4, 8,…,2^k\}$ is closed under multiplication in $\mathbb{Z}/(2^{k+1}-2)\mathbb{Z}$

I've been investigating as part of a project the structure of integers modulo $n$ ($\mathbb{Z}$/n$\mathbb{Z}$) under multiplication. One aspect I'm looking at is, for any natural number $k$, finding a ...
1
vote
0answers
125 views

Order of kernel of a homomorphism

Let $p,q$ be distinct primes. Prove that the kernel of the map $$f: (\mathbb{Z}/p^k\mathbb{Z})^* \rightarrow (\mathbb{Z}/p^k\mathbb{Z})^*$$ defined by $f(x)=x^q$ has order $\gcd(p-1,q).$ Thank ...
4
votes
4answers
105 views

What prerequisite knowledge is needed to understand “Multiplicative group of integers modulo n”

I want to self teach myself Multiplicative group of integers modulo n since it's a foundation in cryptography, IT Security, and Microsoft's UProve technology. When I go to the Wikipedia page I am ...
0
votes
3answers
1k views

Show that a map is well-defined and homomorphism

Define a function $f_n:\mathbb{Z}_m \to \mathbb{Z}_m$ as a map $\bar{a}\mapsto n\cdot \bar{a}$. Show that it is both well-defined and a group homomorphism. For the well-defined part, I know that I ...
1
vote
3answers
237 views

Question about rings and modulo multiplication tables

Why is 2=0 in K for part a)? Also I don't understand what part b) is asking you to do - what does it mean by alpha = [X], so M=etc. Could someone please explain the question and the solutions to part ...
1
vote
2answers
117 views

Modular Arithmetic and the Order of the Monster

I am trying to verify directly using modular arithmetic that $|M|/(40*41) \equiv 1$ mod $41$, where $M$ is the monster group. I am not really sure how to approach this type of problem, i.e. one ...
1
vote
1answer
582 views

Solving a polynomial modulo an integer

Say I have a polynomial $F$ of degree $n$ with coefficients in $Z_m$ and I wish to find $x$ such that $F(x)=0$ (mod $m$). For instance if $F(x)=x^{2}-a$ the solution would be the modulo $m$ squareroot ...
2
votes
4answers
699 views

Checking if a set is closed under modular multiplication

I have to check if the set {1, 3, 7, 9, 11, 13, 17, 19} forms a group under multiplication modulo 20, and the only idea that I've had so far is: attempt brute force on all the elements (multiplying ...
3
votes
0answers
151 views

Number of elements in projective special linear group over $\mathbb{Z}/n\mathbb{Z}$

While reading a paper about the modular group $\Gamma = PSL_2(\mathbb{Z})$, I came upon the following sentence ($\Gamma(N)$ is the kernel of the canonical map $PSL_2(\mathbb{Z}) \rightarrow ...
4
votes
1answer
200 views

Fermat's little theorem for $n=3$

for $N > 0$, I'm trying to show Fermat's little theorem, for $3$ using the orbit stabilizer theorem: $N^3 - N$ an element of $3\mathbb{Z}\ (3 \mod \mathbb{Z})$ Pf/ we can break it down into ...
1
vote
1answer
342 views

Breaking RSA in a special case

This is a part of homework assignment, and I am stuck. The RSA signature is being calculated using Chinese Remainder theorem technique. Find the detailed description here. Public and private keys are ...