Fdtxjr

Project Euler #1 in C++

Who can remove European Commissioners?

Would it be possible to dictate a bech32 address as a list of English words?

A term for a woman complaining about things/begging in a cute/childish way

Co-worker has annoying ringtone

Can you explain what "processes and tools" means in the first Agile principle?

Is there hard evidence that the grant peer review system performs significantly better than random?

What is the appropriate index architecture when forced to implement IsDeleted (soft deletes)?

QGIS virtual layer functionality does not seem to support memory layers

Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?

Lagrange four-squares theorem --- deterministic complexity

What order were files/directories outputted in dir?

Take 2! Is this homebrew Lady of Pain warlock patron balanced?

How were pictures turned from film to a big picture in a picture frame before digital scanning?

How to plot logistic regression decision boundary?

Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?

How fail-safe is nr as stop bytes?

How to unroll a parameter pack from right to left

How to play a character with a disability or mental disorder without being offensive?

How to draw/optimize this graph with tikz

Interpretation of R output from Cohen's Kappa

An adverb for when you're not exaggerating

Find 108 by using 3,4,6

Did any compiler fully use 80-bit floating point?

Why is the order of a multiplicative modulo group divisible by the order of an element in its group?

0

0

$begingroup$

In this question:

Find natural numbers $n,m$ such that the residue class $[m]_n in mathbbZ_n$ has order $5$.

My solution was $m = 2$ and $n = 31$ as $2^5 = 32 equiv 1 pmod31$.

However, the solutions stated that:

If $(mathbbZ_n, times)$ has an element of order $5$, then we know that its order is divisible by $5$.

Is my answer not a counter-example to this statement?

group-theory finite-groups modular-arithmetic

share|cite|improve this question

edited Mar 27 at 21:01

gt6989b

36k22557

asked Mar 27 at 20:55

ShreeShree

134

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The order of $BbbZ_31^*$ is $30$, which is a multiple of five.
  $endgroup$
  – Jyrki Lahtonen
  Mar 27 at 20:59
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The multiplicative group of integers $pmod 31$ has order $30$.
  $endgroup$
  – lulu
  Mar 27 at 21:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh, I completely forgot that [31] is not an element. Thanks for the quick reply!
  $endgroup$
  – Shree
  Mar 27 at 21:02
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  By Lagrange, the order of an element divides the order of the group, i.e., $5mid 30$. Here we have $phi(31)=30$.
  $endgroup$
  – Dietrich Burde
  Mar 27 at 21:10
  
  

  
  
  
  

add a comment | 

0

0

$begingroup$

In this question:

Find natural numbers $n,m$ such that the residue class $[m]_n in mathbbZ_n$ has order $5$.

My solution was $m = 2$ and $n = 31$ as $2^5 = 32 equiv 1 pmod31$.

However, the solutions stated that:

If $(mathbbZ_n, times)$ has an element of order $5$, then we know that its order is divisible by $5$.

Is my answer not a counter-example to this statement?

group-theory finite-groups modular-arithmetic

share|cite|improve this question

edited Mar 27 at 21:01

gt6989b

36k22557

asked Mar 27 at 20:55

ShreeShree

134

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The order of $BbbZ_31^*$ is $30$, which is a multiple of five.
  $endgroup$
  – Jyrki Lahtonen
  Mar 27 at 20:59
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The multiplicative group of integers $pmod 31$ has order $30$.
  $endgroup$
  – lulu
  Mar 27 at 21:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh, I completely forgot that [31] is not an element. Thanks for the quick reply!
  $endgroup$
  – Shree
  Mar 27 at 21:02
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  By Lagrange, the order of an element divides the order of the group, i.e., $5mid 30$. Here we have $phi(31)=30$.
  $endgroup$
  – Dietrich Burde
  Mar 27 at 21:10
  
  

  
  
  
  

add a comment | 

$begingroup$

In this question:

Find natural numbers $n,m$ such that the residue class $[m]_n in mathbbZ_n$ has order $5$.

My solution was $m = 2$ and $n = 31$ as $2^5 = 32 equiv 1 pmod31$.

However, the solutions stated that:

If $(mathbbZ_n, times)$ has an element of order $5$, then we know that its order is divisible by $5$.

Is my answer not a counter-example to this statement?

group-theory finite-groups modular-arithmetic

share|cite|improve this question

edited Mar 27 at 21:01

gt6989b

36k22557

asked Mar 27 at 20:55

ShreeShree

134

$endgroup$

share|cite|improve this question

edited Mar 27 at 21:01

gt6989b

36k22557

asked Mar 27 at 20:55

ShreeShree

134

share|cite|improve this question

edited Mar 27 at 21:01

gt6989b

36k22557

asked Mar 27 at 20:55

ShreeShree

134

edited Mar 27 at 21:01

gt6989b

36k22557

edited Mar 27 at 21:01

gt6989b

36k22557

asked Mar 27 at 20:55

ShreeShree

134

asked Mar 27 at 20:55

ShreeShree

134

2 Answers
2

active

oldest

votes

1

$begingroup$

The Lagrange Theorem for groups helps here: the element in question generates a subgroup. The order of the element is the order of the subgroup. The order of the subgroup divides that of the group, by Lagrange's theorem.

share|cite|improve this answer

answered Mar 27 at 21:32

avsavs

4,295515

$endgroup$

add a comment | 

0

$begingroup$

Here's an easier explanation. Note, $1^b=1$ for any integer b. This means once you get to 1, you can power your result to any power. Modular
arithmetic groups, obey normal arithmetic, otherwise they wouldn't be useful in disproving numerical results. Your order is an exponent, by the exponent rule $(x^y)^z=x^ycdot z$, we get the same result as multiplying your order by anything. This makes them congruent to each other, and to 1. Therefore any multiple of an order of 1 mod something, is also an exponent that produces 1 for the base used. The order of the group, is the highest exponent required to make any base element get to 1. After getting to one the congruences repeat, so the group order, must be a multiple of every element's individual orders.

share|cite|improve this answer

answered Mar 29 at 2:04

Roddy MacPheeRoddy MacPhee

929118

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3165123%2fwhy-is-the-order-of-a-multiplicative-modulo-group-divisible-by-the-order-of-an-e%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

The Lagrange Theorem for groups helps here: the element in question generates a subgroup. The order of the element is the order of the subgroup. The order of the subgroup divides that of the group, by Lagrange's theorem.

share|cite|improve this answer

answered Mar 27 at 21:32

avsavs

4,295515

$endgroup$

add a comment | 

1

$begingroup$

The Lagrange Theorem for groups helps here: the element in question generates a subgroup. The order of the element is the order of the subgroup. The order of the subgroup divides that of the group, by Lagrange's theorem.

share|cite|improve this answer

answered Mar 27 at 21:32

avsavs

4,295515

$endgroup$

add a comment | 

$begingroup$

The Lagrange Theorem for groups helps here: the element in question generates a subgroup. The order of the element is the order of the subgroup. The order of the subgroup divides that of the group, by Lagrange's theorem.

share|cite|improve this answer

answered Mar 27 at 21:32

avsavs

4,295515

$endgroup$

share|cite|improve this answer

answered Mar 27 at 21:32

avsavs

4,295515

answered Mar 27 at 21:32

avsavs

4,295515

answered Mar 27 at 21:32

avsavs

4,295515

0

$begingroup$

Here's an easier explanation. Note, $1^b=1$ for any integer b. This means once you get to 1, you can power your result to any power. Modular
arithmetic groups, obey normal arithmetic, otherwise they wouldn't be useful in disproving numerical results. Your order is an exponent, by the exponent rule $(x^y)^z=x^ycdot z$, we get the same result as multiplying your order by anything. This makes them congruent to each other, and to 1. Therefore any multiple of an order of 1 mod something, is also an exponent that produces 1 for the base used. The order of the group, is the highest exponent required to make any base element get to 1. After getting to one the congruences repeat, so the group order, must be a multiple of every element's individual orders.

share|cite|improve this answer

answered Mar 29 at 2:04

Roddy MacPheeRoddy MacPhee

929118

$endgroup$

add a comment | 

0

$begingroup$

Here's an easier explanation. Note, $1^b=1$ for any integer b. This means once you get to 1, you can power your result to any power. Modular
arithmetic groups, obey normal arithmetic, otherwise they wouldn't be useful in disproving numerical results. Your order is an exponent, by the exponent rule $(x^y)^z=x^ycdot z$, we get the same result as multiplying your order by anything. This makes them congruent to each other, and to 1. Therefore any multiple of an order of 1 mod something, is also an exponent that produces 1 for the base used. The order of the group, is the highest exponent required to make any base element get to 1. After getting to one the congruences repeat, so the group order, must be a multiple of every element's individual orders.

share|cite|improve this answer

answered Mar 29 at 2:04

Roddy MacPheeRoddy MacPhee

929118

$endgroup$

add a comment | 

$begingroup$

Here's an easier explanation. Note, $1^b=1$ for any integer b. This means once you get to 1, you can power your result to any power. Modular
arithmetic groups, obey normal arithmetic, otherwise they wouldn't be useful in disproving numerical results. Your order is an exponent, by the exponent rule $(x^y)^z=x^ycdot z$, we get the same result as multiplying your order by anything. This makes them congruent to each other, and to 1. Therefore any multiple of an order of 1 mod something, is also an exponent that produces 1 for the base used. The order of the group, is the highest exponent required to make any base element get to 1. After getting to one the congruences repeat, so the group order, must be a multiple of every element's individual orders.

share|cite|improve this answer

answered Mar 29 at 2:04

Roddy MacPheeRoddy MacPhee

929118

$endgroup$

share|cite|improve this answer

answered Mar 29 at 2:04

Roddy MacPheeRoddy MacPhee

929118

answered Mar 29 at 2:04

Roddy MacPheeRoddy MacPhee

929118

answered Mar 29 at 2:04

Roddy MacPheeRoddy MacPhee

929118