3
votes
1answer
50 views

If $p$ is prime, prove that $\exists k\in\lbrace 5,-7,9,-11,..\rbrace$ in $(\mathbb{Z}/p\mathbb{Z})^*$ so that the Legendre symbol $(\frac{k}{p})=-1$

The BSPW primality test, when given $p$ as input, iterates over $k \in \lbrace 5,-7,9,-11,...\rbrace$ as long as the Legendre symbol $(\frac{k}{p})=1$. If $(\frac{k}{p})=0$, it returns "composite". So ...
2
votes
1answer
28 views

Why does $x^{m \cdot 2^i} \equiv -1$ with odd $m$ imply that $x$ has order $m \cdot 2^{i+1}$?

It is clear that $$x^{m \cdot 2^{i+1}} \equiv 1$$ for odd $m$ but is there a theorem or an obvious reason why $x$ cannot have order smaller than $m \cdot 2^{i+1}$? Context: I am trying to understand ...
1
vote
1answer
23 views

How can i prove that a cartesian product is isomorphic to another cartesian product

$\def\<#1>{\left<#1\right>}\def\Z{\mathbb Z}\<\Z_6, \oplus> \times \<\Z_{10},\oplus>$ is isomorphic to $\<\Z_2, \oplus> \times \<\Z_{30}, \oplus>$ i know i have to ...
0
votes
1answer
62 views

Equations modulo $143$

Let $x=11$ and $y=13$, and $z=xy=143$. (i) Show that $1$, $x+1$, $−1$ and $−(x+1)$ are the $4$ solutions of $n^2 \equiv 1\pmod z$. (ii) Find the coset of $U_z(2)$ consisting of solutions to $n^2 ...
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
96 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
2answers
19 views

prove that $\text{ord}_k(a)\mid \text{ord}_{k+1}(a)$ where $\text{ord}_k(a)$ is the order of a in $\mathbb{Z}_{p^k}^\ast$

$\newcommand{\ordz}[2]{\text{ord}_{#2}(#1)}$ Prove that $\text{ord}_k(a)\mid \text{ord}_{k+1}(a)$ where $\text{ord}_k(a)$ is the order of a in $\mathbb{Z}_{p^m}^\ast$ I thought doing it using ...
2
votes
1answer
80 views

Proof of existence of primitive roots

In my book (Elementary Number Theory, Stillwell), exercise 3.9.1 asks to give an alternative proof of the existence of a primitive root for any prime. Let $p$ be prime, and consider the group ...
1
vote
1answer
35 views

What can we say about this quantity?

Let $\phi(n)$ be the Euler phi-function. If $a>1$ is an integer, then what is the remainder when $\phi(a^n - 1)$ is divided by $n$ in accordance with the Euclidean algorithm?
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 ...
2
votes
1answer
32 views

Solving a divisibility problem using group theory

Inspired by this I decided to show this: Let $P_n=\displaystyle\prod_{1\leq i<j\leq n} \big(x_i-x_j\big)$ where $x_1\,\dots\, x_n$ are arbitrary integers. Prove $n!\,\big|\, 2P_n$. I am ...
1
vote
1answer
34 views

Group actions: orbits equivalent to divisors?

Does there exist a group with a group action, that acts on the set of natural numbers where the orbit of any natural number is the set of its divisors?
6
votes
0answers
36 views

Inverse image of rationals under tangent function is free abelian?

It is easy to see that the set $\{x:\tan x\in \Bbb Q \,\, or\,\, \pm\infty\}$ forms a group under addition. It is a free abelian group?
3
votes
1answer
50 views

Does every finite cyclic group appear as a subgroup of the multiplicative group of a finite field?

Does every finite cyclic group appear as a subgroup of the multiplicative group of a finite field? In other words, given any $d \in \mathbb{N}$, can we find a prime $p$ and $k \in \mathbb{N}$ such ...
0
votes
0answers
68 views

Describing the sequence A224239.

I've been trying to describe mathematically the $n$th term $a_n$ of the sequence A224239. We get $a_n$ by counting the distinct ways to fill an $n\times n$ grid with squares of smaller integer size, ...
4
votes
5answers
117 views

Find the all the pairs $(n,m) \in \mathbb{N} \times \mathbb{N}$ with the property that $ 2^n+3^m $ is divisible by $23$.

Find the all the pairs $(n,m) \in \mathbb{N} \times \mathbb{N}$ with the property that $ 2^n+3^m $ is divisible by $23$. I'm not really sure how to start this one, but since I found it in a book on ...
2
votes
2answers
70 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
2answers
138 views

Does someone know why raising the element of a group to the power of the order of the group yields the identity?

Does someone know the why raising the element of a group to the power of the order of the group yields the identity? By (finite) group I mean a tuple (G,*) that satisfies the following: closure ...
0
votes
1answer
54 views

order of elements in a finite group - Proof

Has anyone an idea how to prove this one?? If $G$ is a finite group and $a$ is an element of $G$ with $\mathrm{ord}(a) = r$., then $\mathrm{ord}(a^k) = \dfrac{r}{\gcd(r,k)}$. Thank you in ...
2
votes
0answers
37 views

Multiplicative Order Modulo Evaluated Cyclotomic Polynomials

If $\Phi_n(x)$ is the $n$th cyclotomic polynomial, then for which positive integers $n$ and $a>1$ is it true that $\operatorname{ord}_{\Phi_n(a)}(a) = n;$ that is, when is $n$ the smallest positive ...
3
votes
2answers
96 views

2 is a primitive root mod $3^h$ for any positive integer $h$

It's easy to verify that 2 is a primitive root mod $3^2$. But then why does it follow that 2 is a primitive root mod $3^h$ for any positive integer $h$? This was used in the solution of 2009 Putnam ...
0
votes
1answer
56 views

Kernel of a homomorphism is subgroup of squares

Let $\gamma:(\mathbb{Z}/p^m\mathbb{Z})^*\rightarrow \{1,-1\}$ be defined as $\gamma(a)=(\frac{a}{p})$, the Legendre symbol; $p$ is an odd prime, and $m$ is an integer greater or equal to $1$. I have ...
1
vote
1answer
28 views

Index relation between two primitive roots

Let n be a positive integer, and x an integer such that gcd(n, x)=1. Suppose g and h are primitive roots mod n. Show that: $ind_{h}(x) = ind_{h}(g) \cdot ind_{g}(x) (mod {\phi}(n))$ I've been ...
2
votes
1answer
72 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
51 views

Cyclicity of finite group

If $g$ is a primitive root of $p$ (i.e. $\mathbb{F}_p^{\times}=\langle g \rangle$) show that two consecutive powers of $g$ have consecutive least residues. That is, show that there exists $k$ such ...
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 ...
1
vote
1answer
71 views

Calculating elements of a particular order

$\newcommand{\ord}{\operatorname{ord}}$ To find all the elements in $(\mathbb Z_{10009}^*,\cdot)$ of order $72$ (without an exhaustive search), I have proceeded in the following manner : For a ...
0
votes
1answer
51 views

If $g$ has order $n$, and $g^m=e$, then $n\mid m$

Let $G$ be a group and $g\in G$ an element of order $n$, i.e. $g^n=e$ but $g^p\neq e$ for any $0<p<n$. Show if $g^m=e$, then $n\mid m$. I want to use $m=qn+r$ with $0\leq r< n$.
2
votes
1answer
73 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 ...
2
votes
2answers
101 views

$(\Bbb Z[x]/(x^{n+1}))^\times\cong\Bbb Z/2\Bbb Z \times \prod _{i=1}^n \Bbb Z$ [duplicate]

I'm trying to prove the group isomorphism $(\Bbb Z[x]/(x^{n+1}))^\times\cong\Bbb Z/2\Bbb Z \times \prod _{i=1}^n \Bbb Z$. Obviously I tried to establish a ring isomorphism from $\Bbb Z[x]/(x^{n+1})$ ...
3
votes
1answer
86 views

Showing that a homomorphism between groups of units is surjective.

Let $n$ be a positive integer and let $d$ be some divisor of $n$. Consider the group of units modulo $n$, which we shall denote by $U(n)$. Likewise, denote the group of units modulo $d$ by $U(d)$. ...
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
96 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 ...
4
votes
2answers
66 views

Finding all integers $n$ such that $\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ has exponent $2$

This problem is from a past qualifying exam. Definition A group $G$ has exponent $e$ if $g^e=1$ for all $g\in G$. Problem Let $G=\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$. Find all the ...
1
vote
0answers
42 views

The cosets of $\mathbb{nZ}$

I'd like to show that the only cosets of $\mathbb{nZ}$ are $\bar a$ for $a=0,1,\dots,n-1$ where $\bar a$ denotes the equivalence class containing $a$. Proof. Any integer $x$ can be written as ...
2
votes
1answer
54 views

Counting an orbit length in $\mathbb{Z}/q^{\alpha}\mathbb{Z}$

After working a lot of examples, I came up with the following conjecture: "Let $p, q$ be unequal primes, and $\alpha \geq 0, a$ integers. Suppose $l > 1$ is the multiplicative order of $p$ modulo ...
2
votes
3answers
108 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 ...
10
votes
1answer
497 views

Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?

Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, ...
-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
207 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 ...
2
votes
2answers
67 views

Order of a group?

Let $a = g^{16}$. Assume $\operatorname{ord} g = 40$. Find $\operatorname{ord} a$. Not sure how you would find $\operatorname{ord}a$. We did not go over this. Here is what I did We know that ...
2
votes
0answers
117 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 ...
0
votes
1answer
65 views

If ord (g) is d and $d_0$/d then ord ($g^{d_0}$) is d/$d_0$.

Let's give $ord(g)$ the name $d$. Let $d_0$ be some integer. Lemma: Let $ord (g)$ be $d$ and let $d_0$/$d$, then $ord$ ($g^{d_0}$) is d/$d_0$. I think this is saying once we know that $d_0$/$d$ ...
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 ...
3
votes
2answers
184 views

Is my proof that $U_{pq}$ is not cyclic if $p$ and $q$ are distinct odd primes correct?

Prove that $U_{pq}$ is not cyclic if $p$ and $q$ are distinct odd primes. I am a self taught person. I just learned this and tried this on my own and came up with this. $x \equiv 1 \pmod{p}$ and ...
4
votes
3answers
327 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 ...
2
votes
0answers
64 views

Show that if $1+\frac {1}{2}+\frac{1}{3}+\cdots +\frac {1}{p-1}=\frac {a}{b}$then a is divisible by $p^2$ [duplicate]

Here $p$ is a prime number, grater than 3. I can not understand how do I start.Actually I found this problem from Herstein of page 112.I need some hints plz.. Edit : The original post said ...
2
votes
3answers
454 views

Proof of Fermat's little theorem using groups

I am trying to prove Fermat's little theorem using groups. Here is my proof: Let $p$ be a prime. Since all numbers a such that $1\leq a\leq p-1$ are relatively prime with $p$, they form a group under ...
0
votes
3answers
146 views

Weird Sub-ring/field? question

Let $R=\{\frac{n}{10^{k}} \mid (n,k) \in Z, k>-1\}$ which is the sub-ring of the Rational numbers ( assumed true) Consider S a subset of R $S= \{(3/10),(33/100),(333/100),...\}$ Show that this ...
7
votes
4answers
684 views

Congruent Modulo $n$: definition

In an Introduction to Abstract Algebra by Thomas Whitelaw, he gives examples of the congruence mod operation, such as $13 \equiv5 \pmod4$, and $9 \equiv -1 \pmod 5$. But when I first learned about ...