Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [multiplicative-order]

The tag has no usage guidance.

0
votes
3answers
31 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}\...
1
vote
1answer
20 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 ...
0
votes
0answers
31 views

Detect if an element is in an orbit.

Suppose $n = pq$ is a product of two distinct primes. We also know that integer $r$ divides $\varphi(n) = (p-1)(q-1)$ and $r^2$ doesn't divide it. Fix element $x$ of $\mathbb{Z}_{n}$. Can we tell ...
0
votes
0answers
20 views

Confused about Matrix Multiplication like when to use Row times Column and Column times Row

I am really confused about when to use Row times Column and Column times Row. In the picture, if you want to Matrix Multiplication of AB, you do Row times Column but if you wanna do Matrix ...
0
votes
0answers
56 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 ...
0
votes
1answer
33 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 ...
0
votes
1answer
192 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 ...
2
votes
1answer
35 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, $...
4
votes
0answers
65 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}\...
2
votes
1answer
42 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 ...
2
votes
3answers
102 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^{...
9
votes
1answer
686 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 ...
2
votes
1answer
34 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 ...
0
votes
2answers
33 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?
0
votes
1answer
239 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, ...
0
votes
1answer
144 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 ...
0
votes
0answers
49 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 ...
4
votes
3answers
199 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 ...
1
vote
0answers
66 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 ...
0
votes
2answers
847 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 ...
0
votes
2answers
91 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 ...
0
votes
0answers
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$ ...
0
votes
1answer
77 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}...
0
votes
0answers
46 views

$ord_{n}(k) = \infty$?

For example: $14^{0} \pmod 2 = 1$ $14^{1} \pmod 2 = 0$ $14^{2} \pmod 2 = 0$ ... They will never be achieved again number one. So $ord_{2}(14) = \infty$? When $ord_{n}(k) = \infty$?
3
votes
1answer
95 views

Number of distinct remainders modulo n smaller than Euler's totient function

How come that the number of distinct remainders $a_{k}$ for $g^{k}\equiv a_{k} \mod (n)$ for specific positive $n$ and any positive $g$ and $k=1,2,3...$ is never greater than $\varphi (n)$ (Euler's ...
3
votes
0answers
73 views

How quickly can we find a value that has large multiplicative order modulo $n$?

If we're trying to find an element modulo $n$ that has multiplicative order at least $\sqrt{n}$, how quickly can we do this? We don't know if $n$ is prime or composite, only that $n$ definitely has a ...
1
vote
1answer
47 views

Using simple matrix algebra to solve for a specific matrix (Beginner question)

The matrix $AB = C$ where $A$, $B$ and $C$ are all $2 \times 2$ non-singular matrices. How would I go about to solve for the Matrix $A$ and express it in terms of $B$ and $C$? There are two methods ...
0
votes
2answers
133 views

can composite groups have primitive roots (be cyclic)?

Imagine Z/nZ with n not prime (n=pq). Can the multiplicative group be cyclic? I read the paper over here: http://math.uga.edu/~pete/4400primitiveroots.pdf At one point he dismiss the case where the ...
1
vote
2answers
236 views

Primitive roots generated from a primitive root

Let $p$ be a prime number, and let $a$ be a primitive root $\mod p$. Is it true that $a^m$ is a primitive root if and only if $\gcd(m,p-1)=1$? One direction is correct: if $a^m$ is a primitive root, ...
3
votes
1answer
99 views

Why does $\equiv 1\ (\text{mod}\ n)$ seem so important?

I'm not great with math so please feel free to correct any mistakes in my question (or add more examples). I'm a software engineer and have recently wanted to better understand the maths behind RSA ...
0
votes
2answers
33 views

Should the order of $a^k$ be $h/k$ as opposed to $h/(h,k)$?

Previously shown: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ s.t. $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists and $d\mid\phi(m)$. Moreover, whenever $a^k\equiv 1\pmod{m}$, one has $d\mid k$...
1
vote
2answers
69 views

Problem in proof of: Show the order $d$ of $a$ modulo $m$ exists and $d\mid\phi(m)$

Theorem: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ satisfy $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists, and $d\mid\phi(m)$. Proof: By Euler's theorem, one has $a^{\phi(m)}\equiv 1\pmod{m}$,...
1
vote
1answer
469 views

Showing multiplicative inverse has the same order $\pmod{p}$?

Suppose that $a$ has order $h \pmod{p}$ and $a\overline{a} \equiv 1 \pmod{p}$. Show $\overline{a}$ also has order $h$. I'm a little confused as to how to start proving this -- I know that if $a$ has ...
1
vote
2answers
52 views

Proof relating to the order of $a \mod n$?

The proof required is to show that $\operatorname{ord}_n(a^j) \mid\operatorname{ord}_n(a)$, for any positive integer $j$. I have considered using a proof by contradiction, but am having trouble going ...
2
votes
1answer
106 views

If $(ord_m(a), ord_m(b)) = 1$ prove that $ord_m(ab) = ord_m(a)*ord_m(b) $

$\DeclareMathOperator\ord{ord}$Let $a, b$, and $m$ be positive integers such that $(a,m) = (b,m) = 1$. Assume that $(\ord_m(a), \ord_m(b)) = 1$. Prove that $\ord_m(ab) = \ord_m(a)*\ord_m(b)$. So I ...
3
votes
2answers
111 views

Showing $\operatorname{ord}_ma^s=k$ if $\gcd(s,k) = 1$ and $\operatorname{ord}_ma=k$

If $\operatorname{ord}_ma=k$ and if $\gcd(s,k)=1$ for some $s\ge1$, prove that $\operatorname{ord}_ma^s=k$. I know that $a^n\equiv 1 \pmod m$ for $n \ge 1$ if and only if $k\mid n$. However, I don't ...