Skip to main content

Questions tagged [multiplicative-order]

Let $G$ be a finite group, typically $\mathbb{Z}/n \mathbb{Z}$, and $g\in G$. The multiplicative order of $g$ is the least $n\in\mathbb{N}^+$ such that $g^n = e$, the identity of $G$.

Filter by
Sorted by
Tagged with
1 vote
1 answer
23 views

Properties of matrices with a multiplicative order

I have been trying to find any article or sources talking about the structure and properties of matrices with a multiplicativw order, i.e. a matrix $A$ has a multiplicative order of $n$ if and only if ...
IV-301's user avatar
  • 49
1 vote
0 answers
41 views

Infinite sequence of integers $\{m_n\}$ for which the orders of both 2 and 3 are small modulo $m_n$.

It is easy to create a sequence $\{m_n\}$ for which the order of $2\pmod{m_n}$ is as small as possible, i.e. it is about $\log_2(m_n)$. For example $m_n=2^n-1$ is an appropriate sequence. But if I ...
László Remete's user avatar
0 votes
1 answer
134 views

n = pq where p and q are odd prime numbers, gcd(c,n) = 1, c < n, show at most $\frac{φ(n)}{4}$ of c satisfy $ord_n(c)$ is odd

Suppose n = pq where p and q are distinct odd prime numbers. Show that, out of the φ(n) different integers c satisfying 1 < c < n and gcd(c,n) = 1, at most $\frac{φ(n)}{4}$ of them have the ...
Mzq's user avatar
  • 252
3 votes
0 answers
159 views

Why is the multiplicative order of perfect powers modulo $p$ smaller on average?

I've been trying to analyse by myself for recreational purposes what would be a "better" base to use instead of the common decimal one. Part of what should make a base better is to have ...
WordP's user avatar
  • 507
0 votes
4 answers
97 views

$m+1$ generates the kernel of $Z_n^\times\to Z_m^\times$ where $m\mid n$ with the same prime factors

Suppose $m\mid n$. Using the First Isomorphism Theorem with respect to the homomorphism $$\begin{array}{rccc}f:&\mathbb{Z}_n^\times&\to&\mathbb{Z}_m^\times \\&x&\mapsto &x\bmod ...
Joseph Johnston's user avatar
3 votes
0 answers
54 views

About order of a number modulo 2. [duplicate]

For $a, m, n \in \mathbb{N}$, prove that $$\gcd(a^{2^m} + 1, a^{2^n} + 1) = \begin{cases} 1, & \text{if $a$ is even}\\ 2, & \text{if $a$ is odd} \end{cases}$$ given $m \ne n$. My attempt: ...
Nick Larry's user avatar
2 votes
1 answer
589 views

Multiplicative order of $2$ modulo $p$.

When calculating the multiplicative order of $2$ modulo a prime $p$ you often get $p-1$ or $\frac{p-1}{2}$ as a result, but there are cases where this does not hold, is there a general form for those ...
Emilio Junoy's user avatar
0 votes
1 answer
53 views

When $\text{ord}_n(p)/m = \text{ord}_{n/m}(p)=1$

$\newcommand\ord{\text{ord}}$ For integers $n,m,p$, suppose $m$ and $n$ share the same prime divisors with $m$ dividing $n$, and suppose $\text{gcd}(p,n)=1$. I want to show that $\ord_n(p)/m=\ord_{n/m}...
Joseph Johnston's user avatar
-2 votes
1 answer
67 views

Roots of unity over finite fields

Let $H = \{\omega, \omega^2, \dots, \omega^{n-1}, \omega^n = 1\}$ be the multiplicative subgroup of $\mathbb{Z}_p$ of $n$-th roots of unity, generated by the primitive $n$-th root of unity $\omega$. I ...
Bean Guy's user avatar
  • 321
1 vote
1 answer
62 views

Multiplicative Order when for integers $m > 2, n > 0$, when $2^m | (3^n - 1)$

It seems to me that for integers $m>2, n>0$, when $2^m | (3^n - 1)$, that the multiplicative order is $2^{m-2}$ so that for $0 < i < 2^{m-2}$, $3^i \not\equiv 1 \pmod {2^m}$ and $3^{2^{m-2}...
Larry Freeman's user avatar
2 votes
5 answers
205 views

What is the order of $\bar{2}$ in the multiplicative group $\mathbb Z_{289}^×$?

What is the order of $\bar{2}$ in the multiplicative group $\mathbb Z_{289}^×$? I know that $289 = 17 \times 17$ so would it be $2^8\equiv 256\bmod17 =1$ and therefore the order of $\bar{2}$ is $8$? I'...
ANC420's user avatar
  • 29
4 votes
3 answers
257 views

For which $n$ does $p_n(x)=\sum\limits_{{k=1,(k,n)=1}}^n o(k) x^k $ have exactly two real roots?

Let $n\in\mathbb{N}$ be fixed and denote by $o(k)$ the multiplicative order of $k$ modulo $n$. Define $$p_n(x)=\sum_{\substack{k=1 \\ (k,n)=1}}^n o(k) x^k ;$$here the sum is taken over $k$ that are ...
Integrand's user avatar
  • 8,477
0 votes
2 answers
258 views

What is the order of $\bar{2}$ in the multiplicative group $\mathbb{Z}_{221}^\times$?

What is the order of $\bar{2}$ in the multiplicative group $\mathbb{Z}_{221}^\times$? I keep computing $2^0, 2^1,...$ until we get $1\ (\operatorname{mod} 221)$, but this will take forever! Is there ...
user avatar
0 votes
3 answers
2k views

What is the order of the multiplicative group?

According to Lagrange's Theorem, the multiplicative group $(\mathbb{Z}_{54})^\times$ cannot contain a subgroup of which order: A: $9$ B: $18$ C: $6$ D: $12$ I think that it is D because $12$ is not a ...
user avatar
1 vote
1 answer
99 views

Known table of $GF(p)$ and characteristics

Is there a list of Galois Fields, $GF(p)$ and its known multiplicative generator(s), $g$? I know the general case of finding the generators may take long especially for large $p$, but was wondering if ...
vvg's user avatar
  • 3,331
5 votes
2 answers
138 views

Let $p=40k+9$ be prime. Does $10$ always have even order mod $p$?

This came up while answering a question on the period of the decimal expansion of $1/p$. The critical factor was whether the period (aka the order of $10$ mod $p$) is even or odd, equivalently ...
Erick Wong's user avatar
  • 25.3k
2 votes
1 answer
204 views

If p is a prime divisor of the n-th Fermat number, and k is the multiplicative order of 2 mod p then $k|p-1$

In the question Multiplicative order with Fermat numbers, it is established that if p is a prime divisor of the n-th Fermat number $F_n=2^{2^n}+1$ then the multiplicative order of 2 mod p is $k=2^{n+1}...
Anna Naden's user avatar
1 vote
0 answers
114 views

A question about multiplicative order

Assume that the prime factorization of $M=q_1^{e_1}q_2^{e_2}...q_s^{e_s}$, and $p^n$ divides the order of $a \pmod M$, where $p$ is prime, and $gcd(p^n,M)=1$. Now, my question is: How to prove that $p^...
عبد الرحمن رمزي محمود's user avatar
3 votes
1 answer
288 views

How to solve 1990 IMO Q3

For my lesson on order, one of the exercises my teacher gave me was Question 3 of the 1990 IMO paper: Find all integers $n>1$ such that $\frac{2^n+1}{n^2}$ is an integer. My attempt: We have $$n^...
Kyan Cheung's user avatar
  • 3,194
2 votes
0 answers
38 views

Equations over finite fields to prove primality

Inspired by the Eliptic Curve Primality Test, and classical primality tests, I wanted to know if any particular equation (using multivariate polynomials) over finite fields. The group $(\mathbb Z/n\...
J. Linne's user avatar
  • 3,042
3 votes
3 answers
220 views

Proof $\operatorname{ord}_{2^n}(3)=2^{n-2}$

Trying some values it looks to me it should be true that, for $n$ an integer such that $n\geq 3$:$$\operatorname{ord}_{2^n}(3)=2^{n-2}$$ Is it true? If so how can I prove it? I know that $$3^{2^{n-1}}\...
MMM's user avatar
  • 473
1 vote
1 answer
356 views

Odd prime power congruent to 1 modulo large powers of 2

Let $p$ be an odd prime, $n$ an integer. What can we say about the largest integer $k$ such that $p^n \equiv 1 \mod 2^k$? Equivalently, the largest $k$ such that $2^k \mid (p^n - 1)$. I remember ...
frafour's user avatar
  • 3,025
1 vote
0 answers
100 views

A "Multiplicative Order" Bound?

We are given a set of $w$ values, i.e. $\{w_1, w_2, \dots, w_n\}$, and a set of $v$ values $\{v_1, v_2, \dots, v_m\}$. The question is really simply, what is the (average) sum of minimum powers of $v$...
Matt Groff's user avatar
  • 6,119
0 votes
3 answers
84 views

Can someone teach me Lagrange's order theorem with specific numbers and cayley tables [closed]

I am very new to mathematics and number theory. I understood some specifics of Groups, Rings, order of elements, order of group, Multiplicative group mod $N$, $U(N)$, etc., that is needed to ...
C0DEV3IL's user avatar
1 vote
1 answer
60 views

How to interpret or calculate this sum?

I am trying to solve the following mathematical equation: $4[8\sum q_1(1 - q_1).q_2(1-q_2)]$ $q_1$ = is a vector of length $10000$, with values between $0-1$ $q_2$ = is a vector of length $10000$, ...
marb_021's user avatar
2 votes
0 answers
33 views

Constructive or closed-form expression for order $p$ element $x\in\left({\Bbb Z}\over{q\Bbb Z}\right)^\times$ for $p$, $q$ primes, $p\mid q-1$

I was looking for groups with order $pq$ for primes $p$ and $q$, and found that it wasn't too hard to classify all of them up to isomorphism. In particular, if $p=q$ then we have $C_{p^2}$ or $C_p\...
stanley dodds's user avatar
1 vote
0 answers
68 views

What is the largest multiplicative order of an arbitrary natural number $x$ modulo a set of primes?

A set of primes is given that includes all primes $p$ such that $q_1 \le p \le q_2$. Then a natural $x$ is given that is less than $q_2$. Then all of the multiplicative orders of $x$ modulo the ...
Matt Groff's user avatar
  • 6,119
3 votes
0 answers
112 views

Is the average multiplicative order of a finite field often small?

It's possible to collect together all of the elements in a finite field of size $p$, $p$ prime, that have multiplicative order $\le \log{(p)}$, and put them in a set $s$. My question is, how often is ...
Matt Groff's user avatar
  • 6,119
0 votes
1 answer
2k views

What Happens When I Change the Order of Multiplication of a Rotation Matrix

Given an arbitrary 3x3 matrix M and an angle θ I can use this to, we'll say rotate about my space's Z-axis, so I'd create the rotation matrix: $$ R_z = \begin{bmatrix} \cos\theta&-\sin\...
Jonathan Mee's user avatar
0 votes
3 answers
185 views

Multiplicative order when gcd=1

If $a^{n}\equiv 1 \pmod m$, then $aa^{n-1}\equiv 1 \pmod m$, so $a^{n-1}$ is the multiplicative inverse of $a$ modulo $m$ and $\gcd(a,m)=1$. What I don't understand is why $\gcd(a,m)=1$ and $a^{n}\...
AleWolf's user avatar
  • 185
1 vote
1 answer
41 views

proving a lemma for order of an element

Given an integer a and a positive integer n with gcd(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with $a^k \equiv 1 (mod\ n)$ There exist a lemma to this ...
johnyB99's user avatar
0 votes
0 answers
765 views

Finding multiplicative order of a

I'm asked to find the multiplicative order of $a=860$ in $\langle\mathbb{Z}^*_n, \cdot_n, 1\rangle$, where $n=1383$. Knowing that $ord(a)$ has to be a divisor of $\varphi(n)$, I calculate this number ...
Omar Sharaki's user avatar
0 votes
1 answer
45 views

Question about conservation( unchangingness ) of order of modular multiplicative cycle when cycle is multiplied by relatively prime number.

I'm currently trying to learn about totient, while following the proof of the fermat's little theorem I got stuck at some part and that part include a question of title. first, to prevent the confuse ...
WienAudience's user avatar
0 votes
1 answer
806 views

Multiplicative order of 10 modulo p [closed]

While the multiplicative order of $10$ modulo $2$ or $5$ does not exist, the multiplicative order of $10$ modulo $p$ for $p\geq 7$ prime is not necessarily $p-1$ ($2$ for $p=11$, $6$ for $p=13$, and ...
nabu1227's user avatar
  • 879
3 votes
1 answer
139 views

Primes for which the multiplicative order of $2$ is even

Artin's conjecture on primitive roots is, of course, wide open. In fact, as many people on this site are aware, it has yet to be proven that, for even a single $n$ satisfying the relevant hypotheses, $...
M10687's user avatar
  • 3,270
4 votes
0 answers
73 views

Order of subgroup generated by $ \{ 2,...,k \}$ in multiplicative group $(\mathbb{Z}/ N\mathbb{Z})^\times$

Suppose $ \{ 2,3,4,...,k \}$ is such that no element in it is a factor of N. Then is there a way of determining how large $k$ has to be, in order to generate at least half of $(\mathbb{Z}/ \text{N}\...
Massimo Grande's user avatar
2 votes
1 answer
46 views

Each prime $p$ dividing $n$ has some special form

Let $n$ be any integer and $q$ a prime number. Let $m$ be the multiplicative order of $n=a$ $\pmod q$. We want to show that for each prime $p$ dividing $n$, $p^m = 1 \pmod q$. Theorem: Let $n$ be ...
J. Linne's user avatar
  • 3,042
3 votes
3 answers
194 views

What is $\operatorname{ord}_{22}(5^6)$?

Find $\operatorname{ord}_{22}(5^6)$. So, basically we want to find:$$\operatorname*{arg\,min}_k 5^{6k} \equiv 1\pmod {22}$$ I found that $5^5 \equiv 1\pmod {22}$ so I know that for $k=5$ we have $5^{...
Elimination's user avatar
  • 3,160
12 votes
1 answer
2k views

How is moving the last digit of a number to the front and multiplying related to multiplicative orders?

There seems to be a relationship between multiplicative orders modulo $n$ and a puzzle Presh Talwalkar gave a few days ago at https://www.youtube.com/watch?v=1lHDCAIsyb8 I'm hoping someone can give a ...
user avatar
2 votes
1 answer
51 views

Smallest number $n$ such that $1$ $\pmod n$ is not representable by sum of powers of $2$ and $3$

Which is the smallest integer $n$ not divisible by $2$ or $3$ such that there does NOT exist two integers $x$ and $y$ such that $2^x+3^y$ $=$ $1$ $\pmod n$? If it is not $n = 683$ (the multiplicative ...
J. Linne's user avatar
  • 3,042
0 votes
2 answers
47 views

For what $k$ and $n$ we have: $ord_{k}(n) = k-1$?

For what $k$ and $n$ we have: $ord_{k}(n) = k-1$? $gcd(k, n) = 1$ $ord$ is Multiplicative order. Are there any dependencies?
Aurelio's user avatar
  • 489
0 votes
1 answer
419 views

Compute the (multiplicative) order of each $[a]_n$

Compute the (multiplicative) order of each $[a]_n$. $[7]_{55}$ Can anyone help me understand how to solve this kind of notation? I am getting confused because I don't know what $[7]_{55}$ means, I ...
Koalafications's user avatar
0 votes
1 answer
614 views

Proof for OEIS A002326 multiplicative order of 2 (mod 2n - 1)

I am trying to prove the amount of out-shuffles needed to return a for example set of cards to its original state. The sequence I am talking about is the A002326 sequence. If you number for example ...
Raymond's user avatar
  • 155
0 votes
0 answers
59 views

The exponent subgroup $n\Bbb{Z}$ inducing a nontrivial $X^n - 1 = 0$ solution subgroup of $R^{\times}$ for a ring $R$ with $1$.

Let $R$ be a commutative ring and $R^{\times}$ its multiplicative group. Let $H \leqslant R^{\times}$ and $H' \subset \Bbb{Z}$ be the set of exponents $k$ such that the solutions to $X^k = 1$ form ...
HighAsAKiteOnMath's user avatar
4 votes
3 answers
608 views

Prove $p\mid\frac{x^{a}-1}{x-1}$ using Fermat's little theorem [duplicate]

Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^{p} − a $ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed ...
Filip Markoski's user avatar
1 vote
0 answers
114 views

Who has considered the LCM of the multiplicative order of the divisors of p-1, where p is a prime, for which p-1 is square free?

A colleague of mine and I have been considering the behavior of divisors of p-1 with respect to multiplicative order in Z/(p), for primes p with p-1 square free. The least common-multiple of the ...
Airymouse's user avatar
  • 568
0 votes
2 answers
3k views

Order of element in multiplicative group modulo n, where n is not prime

I should calculate order of a givent element of multiplicative group modulo n. This n might, or might not be a prime. I discovered that I can use algorithm 4.79 from Handbook of Applied Cryptography ...
Jan Kalfus's user avatar
0 votes
2 answers
155 views

Intuitive justification of associative law

It has been previously asked how one can see that multiplication of real numbers is associative. The answer given there is this: Let's use the following analogy for the multiplication case; suppose ...
user avatar
0 votes
0 answers
15 views

Computations modulus a polynomial

Let $\lambda$ be in $\mathbb F_{p^\ell}\setminus \{0\}$ where $p$ is prime and $\ell \in \mathbb N_{\ge 1}$, and $j,k$ be three integers. In order to calculate the multiplicative order of $X+\lambda$ ...
E. Joseph's user avatar
  • 14.9k
0 votes
1 answer
117 views

multiplicative order $ord_{a }(k)$ if $gcd (a, k) > 1$

The question concerns the multiplicative order $ord_{a}(k)$ if $gcd (a, k) > 1$. $2^{0} \pmod 4 = 1$ $2^{1} \pmod 4 = 0$ $2^{2} \pmod 4 = 0$ $2^{3} \pmod 4 = 0$ $2^{4} \pmod 4 = 0$ ... $4^{0}...
Aurelio's user avatar
  • 489