properties of the multiplicative order of an integer

Definition.

Let $m>1$ be an integer and let $a$ be another integer relatively prime to $m$ . The order of $a$ modulo $m$ (or the multiplicative order of $a\\mod m$ ) is the smallest positive integer $n$ such that $a^{n}\\equiv 1\\mod m$ . The order is sometimes denoted by $\\operatorname{ord}a$ or $\\operatorname{ord}_{m}a$ .

Proposition.

Let $m$ be a positive integer and suppose that $(a,m)=1$ .

1.
$a^{s}\\equiv 1\\mod m$ if and only if $\\operatorname{ord}a$ divides $s$ . In particular, $\\operatorname{ord}a$ divides $\\phi(m)$ , where $\\phi$ is the Euler phi function.
2.
$a^{s}\\equiv a^{t}\\mod m$ if and only if $s\\equiv t\\mod\\operatorname{ord}a$ .
3.
If $\\operatorname{ord}a=d$ then $\\displaystyle\\operatorname{ord}a^{k}=\\frac{d}{\\gcd(k,d)}$ for any $k\\geq 1$ .
4.
If $\\operatorname{ord}a=d$ and $e$ is a positive divisor of $d$ then $a^{d/e}$ has exact order $e$ .
5.
Suppose $\\operatorname{ord}a=h$ and $\\operatorname{ord}b=k$ with $\\gcd(h,k)=1$ . Then $\\operatorname{ord}(ab)=hk$ .

单词	PropertiesOfTheMultiplicativeOrderOfAnInteger
释义	properties of the multiplicative order of an integer Definition. Let $m>1$ be an integer and let $a$ be another integer relatively prime to $m$ . The order of $a$ modulo $m$ (or the multiplicative order of $a\\mod m$ ) is the smallest positive integer $n$ such that $a^{n}\\equiv 1\\mod m$ . The order is sometimes denoted by $\\operatorname{ord}a$ or $\\operatorname{ord}_{m}a$ . Proposition. Let $m$ be a positive integer and suppose that $(a,m)=1$ . 1. $a^{s}\\equiv 1\\mod m$ if and only if $\\operatorname{ord}a$ divides $s$ . In particular, $\\operatorname{ord}a$ divides $\\phi(m)$ , where $\\phi$ is the Euler phi function. 2. $a^{s}\\equiv a^{t}\\mod m$ if and only if $s\\equiv t\\mod\\operatorname{ord}a$ . 3. If $\\operatorname{ord}a=d$ then $\\displaystyle\\operatorname{ord}a^{k}=\\frac{d}{\\gcd(k,d)}$ for any $k\\geq 1$ . 4. If $\\operatorname{ord}a=d$ and $e$ is a positive divisor of $d$ then $a^{d/e}$ has exact order $e$ . 5. Suppose $\\operatorname{ord}a=h$ and $\\operatorname{ord}b=k$ with $\\gcd(h,k)=1$ . Then $\\operatorname{ord}(ab)=hk$ .
随便看	BirthdayProblem birthday problem BisectorsTheorem bisectors theorem BisimilarAutomata bisimilar automata Bisimulation bisimulation BitwiseAND bitwise AND BitwiseNOT bitwise NOT BitwiseOR bitwise OR BitwiseXOR bitwise XOR Bivector bivector BlackboardBold blackboard bold Blackjack blackjack BlackScholesFormula Black-Scholes formula BlackScholesPDE