Fdtxjr

How do you say "Trust your struggle." in French?

Recursively move files within sub directories

Are hand made posters acceptable in Academia?

Would this string work as string?

Friend wants my recommendation but I don't want to give it to him

How to split IPA spelling into syllables

Can you take a "free object interaction" while incapacitated?

New Order #2: Turn My Way

How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?

Pre-Employment Background Check With Consent For Future Checks

How do I prevent inappropriate ads from appearing in my game?

Can you describe someone as luxurious? As in someone who likes luxurious things?

Highest stage count that are used one right after the other?

Magnifying glass in hyperbolic space

Can a Knock spell open the door to Mordenkainen's Magnificent Mansion?

Reasons for having MCU pin-states default to pull-up/down out of reset

Connection Between Knot Theory and Number Theory

How to test the sharpness of a knife?

What (if any) is the reason to buy in small local stores?

Relations between homogeneous polynomials

What can I do if I am asked to learn different programming languages very frequently?

C++ lambda syntax

How to preserve electronics (computers, ipads, phones) for hundreds of years?

Reason why a kingside attack is not justified

Prove that $k|φ(m)$ [duplicate]

Order of an Element Modulo $n$ Divides $phi(n)$Show that $2^341equiv2pmod341$Gcd, Fermat little theorem and Euler functionAre $a$ and $n$ relatively prime?Demostrating that a number x is the smallest such that 24x mod (59) = 2 mod (59)Prove that for integers $a$, $b$, and $n$, if $a$ and $b$ are each relatively prime to $n$, then the product $ab$ is also relatively prime to $n$.Prove that g is a primitive root modulo m.Need some help with a proof about primitive roots.For a prime of the form $p=2k+1$, show that if $p!!not|a$ and $aequiv b^2!!mod p$, then $a^kequiv1!!mod p$.Prove that it does not exist two number such that $m^2+n^2=6 underbrace 0 cdots 0$Find the remainder when $(34! + 75^37)^39$ is divided by $37$

1

$begingroup$

This question already has an answer here:

• 
  Order of an Element Modulo $n$ Divides $phi(n)$
  
  2 answers
  
  

Suppose $a$ and $m$ are relatively prime and $k$ is the smallest natural number that $a^kequiv1mod m$. Prove that $k|φ(m)$.

This is just a variation of Fermat Theorem, So do I just need to show that $k = m-1$ and how $varphi(m) = (k)(x)$? I dont know how else to prove it

modular-arithmetic

share|cite|improve this question

edited Mar 13 at 19:24

Yadati Kiran

2,1021622

asked Mar 13 at 19:22

Kevin WangKevin Wang

241

New contributor

Kevin Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

marked as duplicate by Bill Dubuque modular-arithmetic
Users with the  modular-arithmetic badge can single-handedly close modular-arithmetic questions as duplicates and reopen them as needed.

StackExchange.ready(function()
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();

);
);
);
Mar 13 at 21:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  $k$ need not equal $m-1$. Consider $3^2 equiv 1 pmod 8$ but $8-1 ne 2$.
  $endgroup$
  – fleablood
  Mar 13 at 19:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  apply division algorithm on φ(m) and k
  $endgroup$
  – DragunityMAX
  Mar 13 at 19:30
  

  
  
  
  

add a comment | 

1

$begingroup$

This question already has an answer here:

• 
  Order of an Element Modulo $n$ Divides $phi(n)$
  
  2 answers
  
  

Suppose $a$ and $m$ are relatively prime and $k$ is the smallest natural number that $a^kequiv1mod m$. Prove that $k|φ(m)$.

This is just a variation of Fermat Theorem, So do I just need to show that $k = m-1$ and how $varphi(m) = (k)(x)$? I dont know how else to prove it

modular-arithmetic

share|cite|improve this question

edited Mar 13 at 19:24

Yadati Kiran

2,1021622

asked Mar 13 at 19:22

Kevin WangKevin Wang

241

New contributor

Kevin Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

marked as duplicate by Bill Dubuque modular-arithmetic
Users with the  modular-arithmetic badge can single-handedly close modular-arithmetic questions as duplicates and reopen them as needed.

StackExchange.ready(function()
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();

);
);
);
Mar 13 at 21:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  $k$ need not equal $m-1$. Consider $3^2 equiv 1 pmod 8$ but $8-1 ne 2$.
  $endgroup$
  – fleablood
  Mar 13 at 19:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  apply division algorithm on φ(m) and k
  $endgroup$
  – DragunityMAX
  Mar 13 at 19:30
  

  
  
  
  

add a comment | 

$begingroup$

This question already has an answer here:

• 
  Order of an Element Modulo $n$ Divides $phi(n)$
  
  2 answers
  
  

Suppose $a$ and $m$ are relatively prime and $k$ is the smallest natural number that $a^kequiv1mod m$. Prove that $k|φ(m)$.

This is just a variation of Fermat Theorem, So do I just need to show that $k = m-1$ and how $varphi(m) = (k)(x)$? I dont know how else to prove it

modular-arithmetic

share|cite|improve this question

edited Mar 13 at 19:24

Yadati Kiran

2,1021622

asked Mar 13 at 19:22

Kevin WangKevin Wang

241

New contributor

Kevin Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

edited Mar 13 at 19:24

Yadati Kiran

2,1021622

asked Mar 13 at 19:22

Kevin WangKevin Wang

241

New contributor

Kevin Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

edited Mar 13 at 19:24

Yadati Kiran

2,1021622

asked Mar 13 at 19:22

Kevin WangKevin Wang

241

New contributor

Kevin Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited Mar 13 at 19:24

Yadati Kiran

2,1021622

edited Mar 13 at 19:24

Yadati Kiran

2,1021622

asked Mar 13 at 19:22

Kevin WangKevin Wang

241

New contributor

Kevin Wang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked Mar 13 at 19:22

Kevin WangKevin Wang

241

3 Answers
3

active

oldest

votes

2

$begingroup$

If $gcd(a,m)=1,$ then $ain U_m,$ where $U_m$ is the group of units in $mathbbZ_m.$ So use these facts:

• 
  $|U_m|=varphi(m)$


• $ain Gimplies |a|;textdivides; |G|$

share|cite|improve this answer

edited Mar 13 at 19:43

J. W. Tanner

3,4601320

answered Mar 13 at 19:29

Yadati KiranYadati Kiran

2,1021622

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Note that the question is tagged 'modular-arithmetic" so it is likely that the OP has not yet studied group theory (If they had the answer would be obvious)
  $endgroup$
  – Bill Dubuque
  Mar 13 at 21:07
  

  
  
  
  

add a comment | 

1

$begingroup$

Let $G=U(Bbb Z/m)$. We know that $|G|=phi(m)$. The order of the element $ain G$ divides the order of the group by Lagrange. Now we have $a^k=1$ in this group, with $k$ minimal. This means that $ord(a)=k$. Hence $kmid phi(m)$.

share|cite|improve this answer

answered Mar 13 at 19:51

Dietrich BurdeDietrich Burde

81k648106

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Note that the question is tagged 'modular-arithmetic" so it is likely that the OP has not yet studied group theory (If they had the answer would be obvious)
  $endgroup$
  – Bill Dubuque
  Mar 13 at 21:07
  

  
  
  
  

add a comment | 

0

$begingroup$

You know by Euler's theorem (not FLT because we don't know that $m$ is prime) that $a^phi(m) equiv 1 pmod m$.

But we don't know that $phi(m)$ is the smallest such number and it's easy to find examples where is is not. Say $2^3 equiv 1 pmod 7$ then $3 ne phi (7) = 6$ but we do know $3|6$.

Here's what you should consider.

1: If $a^j equiv b pmod m$ and $a^K equiv 1$ then $a^K+j equiv a^Ka^j equiv a^j equiv bpmod m$.

So 1b: If $a^k equiv 1pmod m$ and $n > k$ then $a^n = a^n-ka^k equiv a^n-k*1 equiv a^n-kpmod m$.

And HINT: If $a^k equiv 1pmod m$ and $a^n equiv 1 pmod m; n > k$ then what is $a^n - kequiv ? pmod m$. Hint to the HINT: $a^n-k*a^k= a^n$.

!!!BIG HINT!!!!

$k le phi(m)$. Let $phi(m) = nk + r; r < k$.

Hint to the !!!BIG HINT!!!!

So $1= a^phi(m) equiv a^nka^r equiv a^rpmod m$.

share|cite|improve this answer

answered Mar 13 at 19:54

fleabloodfleablood

72.8k22788

$endgroup$

add a comment | 

2

$begingroup$

If $gcd(a,m)=1,$ then $ain U_m,$ where $U_m$ is the group of units in $mathbbZ_m.$ So use these facts:

• 
  $|U_m|=varphi(m)$


• $ain Gimplies |a|;textdivides; |G|$

share|cite|improve this answer

edited Mar 13 at 19:43

J. W. Tanner

3,4601320

answered Mar 13 at 19:29

Yadati KiranYadati Kiran

2,1021622

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Note that the question is tagged 'modular-arithmetic" so it is likely that the OP has not yet studied group theory (If they had the answer would be obvious)
  $endgroup$
  – Bill Dubuque
  Mar 13 at 21:07
  

  
  
  
  

add a comment | 

2

$begingroup$

If $gcd(a,m)=1,$ then $ain U_m,$ where $U_m$ is the group of units in $mathbbZ_m.$ So use these facts:

• 
  $|U_m|=varphi(m)$


• $ain Gimplies |a|;textdivides; |G|$

share|cite|improve this answer

edited Mar 13 at 19:43

J. W. Tanner

3,4601320

answered Mar 13 at 19:29

Yadati KiranYadati Kiran

2,1021622

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Note that the question is tagged 'modular-arithmetic" so it is likely that the OP has not yet studied group theory (If they had the answer would be obvious)
  $endgroup$
  – Bill Dubuque
  Mar 13 at 21:07
  

  
  
  
  

add a comment | 

$begingroup$

If $gcd(a,m)=1,$ then $ain U_m,$ where $U_m$ is the group of units in $mathbbZ_m.$ So use these facts:

• 
  $|U_m|=varphi(m)$


• $ain Gimplies |a|;textdivides; |G|$

share|cite|improve this answer

edited Mar 13 at 19:43

J. W. Tanner

3,4601320

answered Mar 13 at 19:29

Yadati KiranYadati Kiran

2,1021622

$endgroup$

share|cite|improve this answer

edited Mar 13 at 19:43

J. W. Tanner

3,4601320

answered Mar 13 at 19:29

Yadati KiranYadati Kiran

2,1021622

edited Mar 13 at 19:43

J. W. Tanner

3,4601320

edited Mar 13 at 19:43

J. W. Tanner

3,4601320

answered Mar 13 at 19:29

Yadati KiranYadati Kiran

2,1021622

answered Mar 13 at 19:29

Yadati KiranYadati Kiran

2,1021622

1

$begingroup$

Let $G=U(Bbb Z/m)$. We know that $|G|=phi(m)$. The order of the element $ain G$ divides the order of the group by Lagrange. Now we have $a^k=1$ in this group, with $k$ minimal. This means that $ord(a)=k$. Hence $kmid phi(m)$.

share|cite|improve this answer

answered Mar 13 at 19:51

Dietrich BurdeDietrich Burde

81k648106

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Note that the question is tagged 'modular-arithmetic" so it is likely that the OP has not yet studied group theory (If they had the answer would be obvious)
  $endgroup$
  – Bill Dubuque
  Mar 13 at 21:07
  

  
  
  
  

add a comment | 

1

$begingroup$

Let $G=U(Bbb Z/m)$. We know that $|G|=phi(m)$. The order of the element $ain G$ divides the order of the group by Lagrange. Now we have $a^k=1$ in this group, with $k$ minimal. This means that $ord(a)=k$. Hence $kmid phi(m)$.

share|cite|improve this answer

answered Mar 13 at 19:51

Dietrich BurdeDietrich Burde

81k648106

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Note that the question is tagged 'modular-arithmetic" so it is likely that the OP has not yet studied group theory (If they had the answer would be obvious)
  $endgroup$
  – Bill Dubuque
  Mar 13 at 21:07
  

  
  
  
  

add a comment | 

$begingroup$

Let $G=U(Bbb Z/m)$. We know that $|G|=phi(m)$. The order of the element $ain G$ divides the order of the group by Lagrange. Now we have $a^k=1$ in this group, with $k$ minimal. This means that $ord(a)=k$. Hence $kmid phi(m)$.

share|cite|improve this answer

answered Mar 13 at 19:51

Dietrich BurdeDietrich Burde

81k648106

$endgroup$

share|cite|improve this answer

answered Mar 13 at 19:51

Dietrich BurdeDietrich Burde

81k648106

answered Mar 13 at 19:51

Dietrich BurdeDietrich Burde

81k648106

answered Mar 13 at 19:51

Dietrich BurdeDietrich Burde

81k648106

0

$begingroup$

You know by Euler's theorem (not FLT because we don't know that $m$ is prime) that $a^phi(m) equiv 1 pmod m$.

But we don't know that $phi(m)$ is the smallest such number and it's easy to find examples where is is not. Say $2^3 equiv 1 pmod 7$ then $3 ne phi (7) = 6$ but we do know $3|6$.

Here's what you should consider.

1: If $a^j equiv b pmod m$ and $a^K equiv 1$ then $a^K+j equiv a^Ka^j equiv a^j equiv bpmod m$.

So 1b: If $a^k equiv 1pmod m$ and $n > k$ then $a^n = a^n-ka^k equiv a^n-k*1 equiv a^n-kpmod m$.

And HINT: If $a^k equiv 1pmod m$ and $a^n equiv 1 pmod m; n > k$ then what is $a^n - kequiv ? pmod m$. Hint to the HINT: $a^n-k*a^k= a^n$.

!!!BIG HINT!!!!

$k le phi(m)$. Let $phi(m) = nk + r; r < k$.

Hint to the !!!BIG HINT!!!!

So $1= a^phi(m) equiv a^nka^r equiv a^rpmod m$.

share|cite|improve this answer

answered Mar 13 at 19:54

fleabloodfleablood

72.8k22788

$endgroup$

add a comment | 

0

$begingroup$

You know by Euler's theorem (not FLT because we don't know that $m$ is prime) that $a^phi(m) equiv 1 pmod m$.

But we don't know that $phi(m)$ is the smallest such number and it's easy to find examples where is is not. Say $2^3 equiv 1 pmod 7$ then $3 ne phi (7) = 6$ but we do know $3|6$.

Here's what you should consider.

1: If $a^j equiv b pmod m$ and $a^K equiv 1$ then $a^K+j equiv a^Ka^j equiv a^j equiv bpmod m$.

So 1b: If $a^k equiv 1pmod m$ and $n > k$ then $a^n = a^n-ka^k equiv a^n-k*1 equiv a^n-kpmod m$.

And HINT: If $a^k equiv 1pmod m$ and $a^n equiv 1 pmod m; n > k$ then what is $a^n - kequiv ? pmod m$. Hint to the HINT: $a^n-k*a^k= a^n$.

!!!BIG HINT!!!!

$k le phi(m)$. Let $phi(m) = nk + r; r < k$.

Hint to the !!!BIG HINT!!!!

So $1= a^phi(m) equiv a^nka^r equiv a^rpmod m$.

share|cite|improve this answer

answered Mar 13 at 19:54

fleabloodfleablood

72.8k22788

$endgroup$

add a comment | 

$begingroup$

You know by Euler's theorem (not FLT because we don't know that $m$ is prime) that $a^phi(m) equiv 1 pmod m$.

But we don't know that $phi(m)$ is the smallest such number and it's easy to find examples where is is not. Say $2^3 equiv 1 pmod 7$ then $3 ne phi (7) = 6$ but we do know $3|6$.

Here's what you should consider.

1: If $a^j equiv b pmod m$ and $a^K equiv 1$ then $a^K+j equiv a^Ka^j equiv a^j equiv bpmod m$.

So 1b: If $a^k equiv 1pmod m$ and $n > k$ then $a^n = a^n-ka^k equiv a^n-k*1 equiv a^n-kpmod m$.

And HINT: If $a^k equiv 1pmod m$ and $a^n equiv 1 pmod m; n > k$ then what is $a^n - kequiv ? pmod m$. Hint to the HINT: $a^n-k*a^k= a^n$.

!!!BIG HINT!!!!

$k le phi(m)$. Let $phi(m) = nk + r; r < k$.

Hint to the !!!BIG HINT!!!!

So $1= a^phi(m) equiv a^nka^r equiv a^rpmod m$.

share|cite|improve this answer

answered Mar 13 at 19:54

fleabloodfleablood

72.8k22788

$endgroup$

share|cite|improve this answer

answered Mar 13 at 19:54

fleabloodfleablood

72.8k22788

answered Mar 13 at 19:54

fleabloodfleablood

72.8k22788

answered Mar 13 at 19:54

fleabloodfleablood

72.8k22788