Is $n^{800}= 1 mod{800}$ given that $n$ is relatively prime to 800? [duplicate]

2

$begingroup$

This question already has an answer here:

• 
  How can I prove the Carmichael theorem
  
  1 answer
  
  

I was playing around with some numbers and it seems that for a lot of numbers that are relatively prime to 800 $$n^{800} = 1 mod{800}$$ is this true in general, or is it just coincidental? Is it true that $$n^k=1 mod{k}$$ where $n,k$ are relatively prime?

modular-arithmetic

share|cite|improve this question

edited Jan 31 at 23:52

Peter Foreman

asked Jan 31 at 23:46

Peter ForemanPeter Foreman

6,5841318

$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();
}
);
});
});
Feb 1 at 0:22

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$
  See Euler's Theorem and Carmichael's Lambda function
  $endgroup$
  – Bill Dubuque
  Jan 31 at 23:54
  
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  See also OEIS sequence A124240
  $endgroup$
  – Robert Israel
  Feb 1 at 0:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Robert, that is very interesting!
  $endgroup$
  – Peter Foreman
  Feb 1 at 0:24
  

  
  
  
  

add a comment | 

2

$begingroup$

This question already has an answer here:

• 
  How can I prove the Carmichael theorem
  
  1 answer
  
  

I was playing around with some numbers and it seems that for a lot of numbers that are relatively prime to 800 $$n^{800} = 1 mod{800}$$ is this true in general, or is it just coincidental? Is it true that $$n^k=1 mod{k}$$ where $n,k$ are relatively prime?

modular-arithmetic

share|cite|improve this question

edited Jan 31 at 23:52

Peter Foreman

asked Jan 31 at 23:46

Peter ForemanPeter Foreman

6,5841318

$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();
}
);
});
});
Feb 1 at 0:22

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$
  See Euler's Theorem and Carmichael's Lambda function
  $endgroup$
  – Bill Dubuque
  Jan 31 at 23:54
  
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  See also OEIS sequence A124240
  $endgroup$
  – Robert Israel
  Feb 1 at 0:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Robert, that is very interesting!
  $endgroup$
  – Peter Foreman
  Feb 1 at 0:24
  

  
  
  
  

add a comment | 

2

2

2

1

$begingroup$

This question already has an answer here:

• 
  How can I prove the Carmichael theorem
  
  1 answer
  
  

I was playing around with some numbers and it seems that for a lot of numbers that are relatively prime to 800 $$n^{800} = 1 mod{800}$$ is this true in general, or is it just coincidental? Is it true that $$n^k=1 mod{k}$$ where $n,k$ are relatively prime?

modular-arithmetic

share|cite|improve this question

edited Jan 31 at 23:52

Peter Foreman

asked Jan 31 at 23:46

Peter ForemanPeter Foreman

6,5841318

$endgroup$

This question already has an answer here:

• 
  How can I prove the Carmichael theorem
  
  1 answer
  
  

I was playing around with some numbers and it seems that for a lot of numbers that are relatively prime to 800 $$n^{800} = 1 mod{800}$$ is this true in general, or is it just coincidental? Is it true that $$n^k=1 mod{k}$$ where $n,k$ are relatively prime?

This question already has an answer here:

• 
  How can I prove the Carmichael theorem
  
  1 answer
  
  

modular-arithmetic

modular-arithmetic

share|cite|improve this question

edited Jan 31 at 23:52

Peter Foreman

asked Jan 31 at 23:46

Peter ForemanPeter Foreman

6,5841318

share|cite|improve this question

edited Jan 31 at 23:52

Peter Foreman

asked Jan 31 at 23:46

Peter ForemanPeter Foreman

6,5841318

share|cite|improve this question

share|cite|improve this question

edited Jan 31 at 23:52

Peter Foreman

edited Jan 31 at 23:52

Peter Foreman

edited Jan 31 at 23:52

Peter Foreman

asked Jan 31 at 23:46

Peter ForemanPeter Foreman

6,5841318

asked Jan 31 at 23:46

Peter ForemanPeter Foreman

6,5841318

asked Jan 31 at 23:46

Peter ForemanPeter Foreman

6,5841318

6,5841318

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();
}
);
});
});
Feb 1 at 0:22

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.

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();
}
);
});
});
Feb 1 at 0:22

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$
  See Euler's Theorem and Carmichael's Lambda function
  $endgroup$
  – Bill Dubuque
  Jan 31 at 23:54
  
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  See also OEIS sequence A124240
  $endgroup$
  – Robert Israel
  Feb 1 at 0:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Robert, that is very interesting!
  $endgroup$
  – Peter Foreman
  Feb 1 at 0:24
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  See Euler's Theorem and Carmichael's Lambda function
  $endgroup$
  – Bill Dubuque
  Jan 31 at 23:54
  
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  See also OEIS sequence A124240
  $endgroup$
  – Robert Israel
  Feb 1 at 0:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Robert, that is very interesting!
  $endgroup$
  – Peter Foreman
  Feb 1 at 0:24
  

  
  
  
  

2

2

$begingroup$
See Euler's Theorem and Carmichael's Lambda function
$endgroup$
– Bill Dubuque
Jan 31 at 23:54

$begingroup$
See Euler's Theorem and Carmichael's Lambda function
$endgroup$
– Bill Dubuque
Jan 31 at 23:54

2

2

$begingroup$
See also OEIS sequence A124240
$endgroup$
– Robert Israel
Feb 1 at 0:02

$begingroup$
See also OEIS sequence A124240
$endgroup$
– Robert Israel
Feb 1 at 0:02

$begingroup$
Thanks Robert, that is very interesting!
$endgroup$
– Peter Foreman
Feb 1 at 0:24

$begingroup$
Thanks Robert, that is very interesting!
$endgroup$
– Peter Foreman
Feb 1 at 0:24

add a comment | 

1 Answer
1

active

oldest

votes

2

$begingroup$

Nice observation! It is true for $800$ but not in general.

The explanation is given by Carmichael's theorem: $a^{lambda(m)} equiv 1 bmod m$ for all $a$ coprime with $m$.

Since $lambda(800)=40$, we have
$a^{800} = (a^{40})^{20} equiv 1^{20} = 1 bmod 800$
for all $a$ coprime with $m$.

share|cite|improve this answer

edited Feb 1 at 0:20

answered Feb 1 at 0:13

lhflhf

167k11172404

$endgroup$

add a comment | 

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

2

$begingroup$

Nice observation! It is true for $800$ but not in general.

The explanation is given by Carmichael's theorem: $a^{lambda(m)} equiv 1 bmod m$ for all $a$ coprime with $m$.

Since $lambda(800)=40$, we have
$a^{800} = (a^{40})^{20} equiv 1^{20} = 1 bmod 800$
for all $a$ coprime with $m$.

share|cite|improve this answer

edited Feb 1 at 0:20

answered Feb 1 at 0:13

lhflhf

167k11172404

$endgroup$

add a comment | 

2

$begingroup$

Nice observation! It is true for $800$ but not in general.

The explanation is given by Carmichael's theorem: $a^{lambda(m)} equiv 1 bmod m$ for all $a$ coprime with $m$.

Since $lambda(800)=40$, we have
$a^{800} = (a^{40})^{20} equiv 1^{20} = 1 bmod 800$
for all $a$ coprime with $m$.

share|cite|improve this answer

edited Feb 1 at 0:20

answered Feb 1 at 0:13

lhflhf

167k11172404

$endgroup$

add a comment | 

2

2

2

$begingroup$

Nice observation! It is true for $800$ but not in general.

The explanation is given by Carmichael's theorem: $a^{lambda(m)} equiv 1 bmod m$ for all $a$ coprime with $m$.

Since $lambda(800)=40$, we have
$a^{800} = (a^{40})^{20} equiv 1^{20} = 1 bmod 800$
for all $a$ coprime with $m$.

share|cite|improve this answer

edited Feb 1 at 0:20

answered Feb 1 at 0:13

lhflhf

167k11172404

$endgroup$

Nice observation! It is true for $800$ but not in general.

The explanation is given by Carmichael's theorem: $a^{lambda(m)} equiv 1 bmod m$ for all $a$ coprime with $m$.

Since $lambda(800)=40$, we have
$a^{800} = (a^{40})^{20} equiv 1^{20} = 1 bmod 800$
for all $a$ coprime with $m$.

share|cite|improve this answer

edited Feb 1 at 0:20

answered Feb 1 at 0:13

lhflhf

167k11172404

share|cite|improve this answer

share|cite|improve this answer

edited Feb 1 at 0:20

edited Feb 1 at 0:20

edited Feb 1 at 0:20

answered Feb 1 at 0:13

lhflhf

167k11172404

answered Feb 1 at 0:13

lhflhf

167k11172404

answered Feb 1 at 0:13

lhflhf

167k11172404

167k11172404

add a comment | 

add a comment | 

This page is only for reference, If you need detailed information, please check here