Number of incongruent integers that have a given order modulo p.

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

So, I'm studying number theory by myself on a book I found on the internet, I'll leave a link to the pdf, the page i'm refering to is page 96, there is this one lemma stated and proved in the book that I seem to not get at all:
"We now prove a lemma that gives us how many incongruent integers can have
a given order modulo p, lemma: let p be a prime and m a positive integer such that p-1=m*k for some integer k, then:

S(m)= |m: 0 < m < p, m ∈ Z| ≤ φ(m)"

I've studied the order of an integer mod m, but i'm not completely sure what he means by "integer with a given order modulo p", does it count how many a's are there such that a^(ordᵖa)≡1 (mod p)?
also, that statement about S(m), could someone try to explain it to me a bit more clearly? i'm really confused...

link of the book's pdf: https://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf

P.S. I'm in 4th year of highschool I'm studying this stuff because I truly love it, so I might not be familiar with some more advanced stuff, but if I have to be honest this is the first theorem of the book that i find kinda strange...

number-theory elementary-number-theory modular-arithmetic

share|cite|improve this question

asked Jul 15 at 12:45

Spasoje Durovic

163

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a fixed $m$, one looks at the set $ a : operatornameord_p a = m$, presumably considering only integers $0 < a < p$. That's those $a$ which have order $m$ (exactly, not just $a^m = 1$, which means the order of $a$ divides $m$). The statement of Lemma 11 is badly mangled, it looks like the author decided to change notation and messed that up. The intended statement is (equivalent to) "… Then $S(m) = lvert a : 0 < a < p, operatornameord_p a = mrvert leqslant phi(m)$." Does that make more sense to you?
  – Daniel Fischer♦
  Jul 15 at 14:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  We always have $a^ord (a)equiv 1 mod p$ because $ord(a)$ is defined as the least $nin Bbb Z^+$ such that $a^nequiv 1 mod p.$
  – DanielWainfleet
  Jul 16 at 2:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It helps to know a result of Fermat: For some $r$ we have $ord(r)=p-1.$ So when $1leq j<p$ there is a unique $n_j$ with $1leq n_jleq p-1$ such that $jequiv r^n_j mod p$.... And the result that if $pnot | ;a$ then $ord(a)|(p-1).$....
  – DanielWainfleet
  Jul 16 at 2:20
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DanielFischer Really appreciate your answer, now i finally understand the lemma, cannot thank you enough!
  – Spasoje Durovic
  Jul 16 at 7:37
  
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

So, I'm studying number theory by myself on a book I found on the internet, I'll leave a link to the pdf, the page i'm refering to is page 96, there is this one lemma stated and proved in the book that I seem to not get at all:
"We now prove a lemma that gives us how many incongruent integers can have
a given order modulo p, lemma: let p be a prime and m a positive integer such that p-1=m*k for some integer k, then:

S(m)= |m: 0 < m < p, m ∈ Z| ≤ φ(m)"

I've studied the order of an integer mod m, but i'm not completely sure what he means by "integer with a given order modulo p", does it count how many a's are there such that a^(ordᵖa)≡1 (mod p)?
also, that statement about S(m), could someone try to explain it to me a bit more clearly? i'm really confused...

link of the book's pdf: https://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf

P.S. I'm in 4th year of highschool I'm studying this stuff because I truly love it, so I might not be familiar with some more advanced stuff, but if I have to be honest this is the first theorem of the book that i find kinda strange...

number-theory elementary-number-theory modular-arithmetic

share|cite|improve this question

asked Jul 15 at 12:45

Spasoje Durovic

163

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a fixed $m$, one looks at the set $ a : operatornameord_p a = m$, presumably considering only integers $0 < a < p$. That's those $a$ which have order $m$ (exactly, not just $a^m = 1$, which means the order of $a$ divides $m$). The statement of Lemma 11 is badly mangled, it looks like the author decided to change notation and messed that up. The intended statement is (equivalent to) "… Then $S(m) = lvert a : 0 < a < p, operatornameord_p a = mrvert leqslant phi(m)$." Does that make more sense to you?
  – Daniel Fischer♦
  Jul 15 at 14:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  We always have $a^ord (a)equiv 1 mod p$ because $ord(a)$ is defined as the least $nin Bbb Z^+$ such that $a^nequiv 1 mod p.$
  – DanielWainfleet
  Jul 16 at 2:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It helps to know a result of Fermat: For some $r$ we have $ord(r)=p-1.$ So when $1leq j<p$ there is a unique $n_j$ with $1leq n_jleq p-1$ such that $jequiv r^n_j mod p$.... And the result that if $pnot | ;a$ then $ord(a)|(p-1).$....
  – DanielWainfleet
  Jul 16 at 2:20
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DanielFischer Really appreciate your answer, now i finally understand the lemma, cannot thank you enough!
  – Spasoje Durovic
  Jul 16 at 7:37
  
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

So, I'm studying number theory by myself on a book I found on the internet, I'll leave a link to the pdf, the page i'm refering to is page 96, there is this one lemma stated and proved in the book that I seem to not get at all:
"We now prove a lemma that gives us how many incongruent integers can have
a given order modulo p, lemma: let p be a prime and m a positive integer such that p-1=m*k for some integer k, then:

S(m)= |m: 0 < m < p, m ∈ Z| ≤ φ(m)"

I've studied the order of an integer mod m, but i'm not completely sure what he means by "integer with a given order modulo p", does it count how many a's are there such that a^(ordᵖa)≡1 (mod p)?
also, that statement about S(m), could someone try to explain it to me a bit more clearly? i'm really confused...

link of the book's pdf: https://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf

P.S. I'm in 4th year of highschool I'm studying this stuff because I truly love it, so I might not be familiar with some more advanced stuff, but if I have to be honest this is the first theorem of the book that i find kinda strange...

number-theory elementary-number-theory modular-arithmetic

share|cite|improve this question

asked Jul 15 at 12:45

Spasoje Durovic

163

So, I'm studying number theory by myself on a book I found on the internet, I'll leave a link to the pdf, the page i'm refering to is page 96, there is this one lemma stated and proved in the book that I seem to not get at all:
"We now prove a lemma that gives us how many incongruent integers can have
a given order modulo p, lemma: let p be a prime and m a positive integer such that p-1=m*k for some integer k, then:

S(m)= |m: 0 < m < p, m ∈ Z| ≤ φ(m)"

I've studied the order of an integer mod m, but i'm not completely sure what he means by "integer with a given order modulo p", does it count how many a's are there such that a^(ordᵖa)≡1 (mod p)?
also, that statement about S(m), could someone try to explain it to me a bit more clearly? i'm really confused...

link of the book's pdf: https://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf

P.S. I'm in 4th year of highschool I'm studying this stuff because I truly love it, so I might not be familiar with some more advanced stuff, but if I have to be honest this is the first theorem of the book that i find kinda strange...

number-theory elementary-number-theory modular-arithmetic

share|cite|improve this question

asked Jul 15 at 12:45

Spasoje Durovic

163

share|cite|improve this question

share|cite|improve this question

asked Jul 15 at 12:45

Spasoje Durovic

163

asked Jul 15 at 12:45

Spasoje Durovic

163

asked Jul 15 at 12:45

Spasoje Durovic

163

163

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a fixed $m$, one looks at the set $ a : operatornameord_p a = m$, presumably considering only integers $0 < a < p$. That's those $a$ which have order $m$ (exactly, not just $a^m = 1$, which means the order of $a$ divides $m$). The statement of Lemma 11 is badly mangled, it looks like the author decided to change notation and messed that up. The intended statement is (equivalent to) "… Then $S(m) = lvert a : 0 < a < p, operatornameord_p a = mrvert leqslant phi(m)$." Does that make more sense to you?
  – Daniel Fischer♦
  Jul 15 at 14:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  We always have $a^ord (a)equiv 1 mod p$ because $ord(a)$ is defined as the least $nin Bbb Z^+$ such that $a^nequiv 1 mod p.$
  – DanielWainfleet
  Jul 16 at 2:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It helps to know a result of Fermat: For some $r$ we have $ord(r)=p-1.$ So when $1leq j<p$ there is a unique $n_j$ with $1leq n_jleq p-1$ such that $jequiv r^n_j mod p$.... And the result that if $pnot | ;a$ then $ord(a)|(p-1).$....
  – DanielWainfleet
  Jul 16 at 2:20
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DanielFischer Really appreciate your answer, now i finally understand the lemma, cannot thank you enough!
  – Spasoje Durovic
  Jul 16 at 7:37
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a fixed $m$, one looks at the set $ a : operatornameord_p a = m$, presumably considering only integers $0 < a < p$. That's those $a$ which have order $m$ (exactly, not just $a^m = 1$, which means the order of $a$ divides $m$). The statement of Lemma 11 is badly mangled, it looks like the author decided to change notation and messed that up. The intended statement is (equivalent to) "… Then $S(m) = lvert a : 0 < a < p, operatornameord_p a = mrvert leqslant phi(m)$." Does that make more sense to you?
  – Daniel Fischer♦
  Jul 15 at 14:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  We always have $a^ord (a)equiv 1 mod p$ because $ord(a)$ is defined as the least $nin Bbb Z^+$ such that $a^nequiv 1 mod p.$
  – DanielWainfleet
  Jul 16 at 2:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It helps to know a result of Fermat: For some $r$ we have $ord(r)=p-1.$ So when $1leq j<p$ there is a unique $n_j$ with $1leq n_jleq p-1$ such that $jequiv r^n_j mod p$.... And the result that if $pnot | ;a$ then $ord(a)|(p-1).$....
  – DanielWainfleet
  Jul 16 at 2:20
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DanielFischer Really appreciate your answer, now i finally understand the lemma, cannot thank you enough!
  – Spasoje Durovic
  Jul 16 at 7:37
  
  

  
  
  
  

For a fixed $m$, one looks at the set $ a : operatornameord_p a = m$, presumably considering only integers $0 < a < p$. That's those $a$ which have order $m$ (exactly, not just $a^m = 1$, which means the order of $a$ divides $m$). The statement of Lemma 11 is badly mangled, it looks like the author decided to change notation and messed that up. The intended statement is (equivalent to) "… Then $S(m) = lvert a : 0 < a < p, operatornameord_p a = mrvert leqslant phi(m)$." Does that make more sense to you?
– Daniel Fischer♦
Jul 15 at 14:32

For a fixed $m$, one looks at the set $ a : operatornameord_p a = m$, presumably considering only integers $0 < a < p$. That's those $a$ which have order $m$ (exactly, not just $a^m = 1$, which means the order of $a$ divides $m$). The statement of Lemma 11 is badly mangled, it looks like the author decided to change notation and messed that up. The intended statement is (equivalent to) "… Then $S(m) = lvert a : 0 < a < p, operatornameord_p a = mrvert leqslant phi(m)$." Does that make more sense to you?
– Daniel Fischer♦
Jul 15 at 14:32

We always have $a^ord (a)equiv 1 mod p$ because $ord(a)$ is defined as the least $nin Bbb Z^+$ such that $a^nequiv 1 mod p.$
– DanielWainfleet
Jul 16 at 2:07

We always have $a^ord (a)equiv 1 mod p$ because $ord(a)$ is defined as the least $nin Bbb Z^+$ such that $a^nequiv 1 mod p.$
– DanielWainfleet
Jul 16 at 2:07

It helps to know a result of Fermat: For some $r$ we have $ord(r)=p-1.$ So when $1leq j<p$ there is a unique $n_j$ with $1leq n_jleq p-1$ such that $jequiv r^n_j mod p$.... And the result that if $pnot | ;a$ then $ord(a)|(p-1).$....
– DanielWainfleet
Jul 16 at 2:20

It helps to know a result of Fermat: For some $r$ we have $ord(r)=p-1.$ So when $1leq j<p$ there is a unique $n_j$ with $1leq n_jleq p-1$ such that $jequiv r^n_j mod p$.... And the result that if $pnot | ;a$ then $ord(a)|(p-1).$....
– DanielWainfleet
Jul 16 at 2:20

@DanielFischer Really appreciate your answer, now i finally understand the lemma, cannot thank you enough!
– Spasoje Durovic
Jul 16 at 7:37

@DanielFischer Really appreciate your answer, now i finally understand the lemma, cannot thank you enough!
– Spasoje Durovic
Jul 16 at 7:37

add a comment | 

active

oldest

votes

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852493%2fnumber-of-incongruent-integers-that-have-a-given-order-modulo-p%23new-answer', 'question_page');

);

Post as a guest

Name Email

active

oldest

votes

active

oldest

votes

active

oldest

votes

active

oldest

votes

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852493%2fnumber-of-incongruent-integers-that-have-a-given-order-modulo-p%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email