Mixing
What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$? [duplicate]
$begingroup$
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
9 answers
I was checking the following Euler's theorem exercise:
What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$?
I've started working from calculating $phi (110) = 40$
Now I'm thinking about applying $mod 121$ but I'm unable to. So now I'm maybe in the wrong way. Any help or clue will be really appreciated.
elementary-number-theory modular-arithmetic
edited Jan 29 at 5:14
Jyrki Lahtonen
110k13172387
asked Jan 29 at 4:49
mrazmraz
44319
$endgroup$
marked as duplicate by Jyrki Lahtonen, Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory 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 9 at 1:37
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.
add a comment |
$begingroup$
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
9 answers
I was checking the following Euler's theorem exercise:
What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$?
I've started working from calculating $phi (110) = 40$
Now I'm thinking about applying $mod 121$ but I'm unable to. So now I'm maybe in the wrong way. Any help or clue will be really appreciated.
elementary-number-theory modular-arithmetic
edited Jan 29 at 5:14
Jyrki Lahtonen
110k13172387
asked Jan 29 at 4:49
mrazmraz
44319
$endgroup$
marked as duplicate by Jyrki Lahtonen, Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory 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 9 at 1:37
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.
1
$begingroup$
"I've started working from calculating ϕ(110)=40" Why? What will that have to do with it? Now, on the other hand what is $phi(121)$? And what will THAT have to do with it?
$endgroup$
– fleablood
Jan 29 at 5:17
1
$begingroup$
Possible duplicate of How do I compute $a^b,bmod c$ by hand?. IM(NS)HO trusted users inclined to answer this, should check out the mother thread. If they have something new to add to it, post there.
$endgroup$
– Jyrki Lahtonen
Jan 29 at 5:26
add a comment |
$begingroup$
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
9 answers
I was checking the following Euler's theorem exercise:
What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$?
I've started working from calculating $phi (110) = 40$
Now I'm thinking about applying $mod 121$ but I'm unable to. So now I'm maybe in the wrong way. Any help or clue will be really appreciated.
elementary-number-theory modular-arithmetic
edited Jan 29 at 5:14
Jyrki Lahtonen
110k13172387
asked Jan 29 at 4:49
mrazmraz
44319
$endgroup$
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
9 answers
I was checking the following Euler's theorem exercise:
What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$?
I've started working from calculating $phi (110) = 40$
Now I'm thinking about applying $mod 121$ but I'm unable to. So now I'm maybe in the wrong way. Any help or clue will be really appreciated.
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
9 answers
elementary-number-theory modular-arithmetic
elementary-number-theory modular-arithmetic
edited Jan 29 at 5:14
Jyrki Lahtonen
110k13172387
asked Jan 29 at 4:49
mrazmraz
44319
edited Jan 29 at 5:14
Jyrki Lahtonen
110k13172387
asked Jan 29 at 4:49
mrazmraz
44319
edited Jan 29 at 5:14
Jyrki Lahtonen
110k13172387
edited Jan 29 at 5:14
Jyrki Lahtonen
110k13172387
edited Jan 29 at 5:14
Jyrki Lahtonen
110k13172387
110k13172387
asked Jan 29 at 4:49
mrazmraz
44319
asked Jan 29 at 4:49
mrazmraz
44319
asked Jan 29 at 4:49
mrazmraz
44319
44319
marked as duplicate by Jyrki Lahtonen, Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory 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 9 at 1:37
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 Jyrki Lahtonen, Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory 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 9 at 1:37
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.
1
$begingroup$
"I've started working from calculating ϕ(110)=40" Why? What will that have to do with it? Now, on the other hand what is $phi(121)$? And what will THAT have to do with it?
$endgroup$
– fleablood
Jan 29 at 5:17
1
$begingroup$
Possible duplicate of How do I compute $a^b,bmod c$ by hand?. IM(NS)HO trusted users inclined to answer this, should check out the mother thread. If they have something new to add to it, post there.
$endgroup$
– Jyrki Lahtonen
Jan 29 at 5:26
add a comment |
1
$begingroup$
"I've started working from calculating ϕ(110)=40" Why? What will that have to do with it? Now, on the other hand what is $phi(121)$? And what will THAT have to do with it?
$endgroup$
– fleablood
Jan 29 at 5:17
1
$begingroup$
Possible duplicate of How do I compute $a^b,bmod c$ by hand?. IM(NS)HO trusted users inclined to answer this, should check out the mother thread. If they have something new to add to it, post there.
$endgroup$
– Jyrki Lahtonen
Jan 29 at 5:26
1
1
$begingroup$
"I've started working from calculating ϕ(110)=40" Why? What will that have to do with it? Now, on the other hand what is $phi(121)$? And what will THAT have to do with it?
$endgroup$
– fleablood
Jan 29 at 5:17
$begingroup$
"I've started working from calculating ϕ(110)=40" Why? What will that have to do with it? Now, on the other hand what is $phi(121)$? And what will THAT have to do with it?
$endgroup$
– fleablood
Jan 29 at 5:17
1
1
$begingroup$
Possible duplicate of How do I compute $a^b,bmod c$ by hand?. IM(NS)HO trusted users inclined to answer this, should check out the mother thread. If they have something new to add to it, post there.
$endgroup$
– Jyrki Lahtonen
Jan 29 at 5:26
$begingroup$
Possible duplicate of How do I compute $a^b,bmod c$ by hand?. IM(NS)HO trusted users inclined to answer this, should check out the mother thread. If they have something new to add to it, post there.
$endgroup$
– Jyrki Lahtonen
Jan 29 at 5:26
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
We need $phi(121)=11cdot10implies a^{110}equiv1pmod{121}$ for $11nmid aiff(a,11)=1$
What if $11mid a?$
answered Jan 29 at 4:50
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
add a comment |
$begingroup$
$phi (110)$ is utterly irrelevent.
Euler's theorem tells us about $a^k pmod {n}$ and how $k$ and $phi(n)$ relate.
$phi (k)$ has got sod all to do with fish and fishsticks.
So we want to know how $110$ and $phi(121)= phi(11^2) = 11(11-1)$ relate.
How do they relate?
....
So we can break your task into the following.
1) Figuring out what $phi(121)=phi(11^2) = 11(11-1)$ is.
2) Figuring how $110$ relates to $phi(121)$. In particular what $100 mod phi(121)$ is.
3) Figuring if $gcd(a,121)=1$ then what is $110 pmod {phi(121)}equiv a^{(110 %{phi(121)})}$ are for the different values of $a$ so that $gcd(a,121) = 1$.
4) Figure out what happens when $gcd(a,121) ne 1$.
Now as the prime factorization of $121 = 11^2$ and $phi(11^2) = 11(11-1)$.....
Those become fairly easy questions.
answered Jan 29 at 5:17
fleabloodfleablood
73.6k22891
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We need $phi(121)=11cdot10implies a^{110}equiv1pmod{121}$ for $11nmid aiff(a,11)=1$
What if $11mid a?$
answered Jan 29 at 4:50
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
add a comment |
$begingroup$
We need $phi(121)=11cdot10implies a^{110}equiv1pmod{121}$ for $11nmid aiff(a,11)=1$
What if $11mid a?$
answered Jan 29 at 4:50
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
add a comment |
$begingroup$
We need $phi(121)=11cdot10implies a^{110}equiv1pmod{121}$ for $11nmid aiff(a,11)=1$
What if $11mid a?$
answered Jan 29 at 4:50
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
We need $phi(121)=11cdot10implies a^{110}equiv1pmod{121}$ for $11nmid aiff(a,11)=1$
What if $11mid a?$
answered Jan 29 at 4:50
lab bhattacharjeelab bhattacharjee
228k15158279
answered Jan 29 at 4:50
lab bhattacharjeelab bhattacharjee
228k15158279
answered Jan 29 at 4:50
lab bhattacharjeelab bhattacharjee
228k15158279
answered Jan 29 at 4:50
lab bhattacharjeelab bhattacharjee
228k15158279
228k15158279
add a comment |
add a comment |
$begingroup$
$phi (110)$ is utterly irrelevent.
Euler's theorem tells us about $a^k pmod {n}$ and how $k$ and $phi(n)$ relate.
$phi (k)$ has got sod all to do with fish and fishsticks.
So we want to know how $110$ and $phi(121)= phi(11^2) = 11(11-1)$ relate.
How do they relate?
....
So we can break your task into the following.
1) Figuring out what $phi(121)=phi(11^2) = 11(11-1)$ is.
2) Figuring how $110$ relates to $phi(121)$. In particular what $100 mod phi(121)$ is.
3) Figuring if $gcd(a,121)=1$ then what is $110 pmod {phi(121)}equiv a^{(110 %{phi(121)})}$ are for the different values of $a$ so that $gcd(a,121) = 1$.
4) Figure out what happens when $gcd(a,121) ne 1$.
Now as the prime factorization of $121 = 11^2$ and $phi(11^2) = 11(11-1)$.....
Those become fairly easy questions.
answered Jan 29 at 5:17
fleabloodfleablood
73.6k22891
$endgroup$
add a comment |
$begingroup$
$phi (110)$ is utterly irrelevent.
Euler's theorem tells us about $a^k pmod {n}$ and how $k$ and $phi(n)$ relate.
$phi (k)$ has got sod all to do with fish and fishsticks.
So we want to know how $110$ and $phi(121)= phi(11^2) = 11(11-1)$ relate.
How do they relate?
....
So we can break your task into the following.
1) Figuring out what $phi(121)=phi(11^2) = 11(11-1)$ is.
2) Figuring how $110$ relates to $phi(121)$. In particular what $100 mod phi(121)$ is.
3) Figuring if $gcd(a,121)=1$ then what is $110 pmod {phi(121)}equiv a^{(110 %{phi(121)})}$ are for the different values of $a$ so that $gcd(a,121) = 1$.
4) Figure out what happens when $gcd(a,121) ne 1$.
Now as the prime factorization of $121 = 11^2$ and $phi(11^2) = 11(11-1)$.....
Those become fairly easy questions.
answered Jan 29 at 5:17
fleabloodfleablood
73.6k22891
$endgroup$
add a comment |
$begingroup$
$phi (110)$ is utterly irrelevent.
Euler's theorem tells us about $a^k pmod {n}$ and how $k$ and $phi(n)$ relate.
$phi (k)$ has got sod all to do with fish and fishsticks.
So we want to know how $110$ and $phi(121)= phi(11^2) = 11(11-1)$ relate.
How do they relate?
....
So we can break your task into the following.
1) Figuring out what $phi(121)=phi(11^2) = 11(11-1)$ is.
2) Figuring how $110$ relates to $phi(121)$. In particular what $100 mod phi(121)$ is.
3) Figuring if $gcd(a,121)=1$ then what is $110 pmod {phi(121)}equiv a^{(110 %{phi(121)})}$ are for the different values of $a$ so that $gcd(a,121) = 1$.
4) Figure out what happens when $gcd(a,121) ne 1$.
Now as the prime factorization of $121 = 11^2$ and $phi(11^2) = 11(11-1)$.....
Those become fairly easy questions.
answered Jan 29 at 5:17
fleabloodfleablood
73.6k22891
$endgroup$
$phi (110)$ is utterly irrelevent.
Euler's theorem tells us about $a^k pmod {n}$ and how $k$ and $phi(n)$ relate.
$phi (k)$ has got sod all to do with fish and fishsticks.
So we want to know how $110$ and $phi(121)= phi(11^2) = 11(11-1)$ relate.
How do they relate?
....
So we can break your task into the following.
1) Figuring out what $phi(121)=phi(11^2) = 11(11-1)$ is.
2) Figuring how $110$ relates to $phi(121)$. In particular what $100 mod phi(121)$ is.
3) Figuring if $gcd(a,121)=1$ then what is $110 pmod {phi(121)}equiv a^{(110 %{phi(121)})}$ are for the different values of $a$ so that $gcd(a,121) = 1$.
4) Figure out what happens when $gcd(a,121) ne 1$.
Now as the prime factorization of $121 = 11^2$ and $phi(11^2) = 11(11-1)$.....
Those become fairly easy questions.
answered Jan 29 at 5:17
fleabloodfleablood
73.6k22891
answered Jan 29 at 5:17
fleabloodfleablood
73.6k22891
answered Jan 29 at 5:17
fleabloodfleablood
73.6k22891
answered Jan 29 at 5:17
fleabloodfleablood
73.6k22891
73.6k22891
add a comment |
add a comment |
1
$begingroup$
"I've started working from calculating ϕ(110)=40" Why? What will that have to do with it? Now, on the other hand what is $phi(121)$? And what will THAT have to do with it?
$endgroup$
– fleablood
Jan 29 at 5:17
1
$begingroup$
Possible duplicate of How do I compute $a^b,bmod c$ by hand?. IM(NS)HO trusted users inclined to answer this, should check out the mother thread. If they have something new to add to it, post there.
$endgroup$
– Jyrki Lahtonen
Jan 29 at 5:26