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$ .
随便看	proof of Dini’s theorem ProofOfDivergenceOfHarmonicSeriesbyGroupingTerms proof of divergence of harmonic series (by grouping terms) ProofOfDivergenceOfHarmonicSeriesbySplittingOddAndEvenTerms proof of divergence of harmonic series (by splitting odd and even terms) ProofOfDivisionAlgorithmForIntegers proof of division algorithm for integers ProofOfDominatedConvergenceTheorem proof of dominated convergence theorem proof of dominated convergence theorem ProofOfDominatedConvergenceTheorem1 ProofOfDoobsInequalities proof of Doob’s inequalities ProofOfDoubleAngleIdentity proof of double angle identity ProofOfDownwardLowenheimSkolemTheorem proof of downward Lowenheim-Skolem theorem ProofOfDulacsCriteria Proof of Dulac’s Criteria proof of d⁢α⁢(X,Y)=X⁢(α⁢(Y)) - Y⁢(α⁢(X)) - α⁢([X,Y]) (global coordinate-free) proof of d⁢α⁢(X,Y)=X⁢(α⁢(Y)) - Y⁢(α⁢(X)) - α⁢([X,Y]) (local coordinates) ProofOfEgorovsTheorem proof of Egorov’s theorem ProofOfEisensteinCriterion proof of Eisenstein criterion