How to solve $108 = m^37 pmod 143$
Clash Royale CLAN TAG#URR8PPP
up vote
-1
down vote
favorite
I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.
modular-arithmetic
 |Â
show 1 more comment
up vote
-1
down vote
favorite
I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.
modular-arithmetic
Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
â Toby Mak
Sep 8 at 3:56
$gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
â Will Jagy
Sep 8 at 3:57
@WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
â Jason Kim
Sep 8 at 4:06
@JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
â Will Jagy
Sep 8 at 4:09
Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
â Jason Kim
Sep 8 at 4:17
 |Â
show 1 more comment
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.
modular-arithmetic
I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.
modular-arithmetic
modular-arithmetic
edited Sep 8 at 15:19
GoodDeeds
10.2k21335
10.2k21335
asked Sep 8 at 3:42
Nick Ryan
11
11
Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
â Toby Mak
Sep 8 at 3:56
$gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
â Will Jagy
Sep 8 at 3:57
@WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
â Jason Kim
Sep 8 at 4:06
@JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
â Will Jagy
Sep 8 at 4:09
Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
â Jason Kim
Sep 8 at 4:17
 |Â
show 1 more comment
Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
â Toby Mak
Sep 8 at 3:56
$gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
â Will Jagy
Sep 8 at 3:57
@WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
â Jason Kim
Sep 8 at 4:06
@JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
â Will Jagy
Sep 8 at 4:09
Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
â Jason Kim
Sep 8 at 4:17
Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
â Toby Mak
Sep 8 at 3:56
Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
â Toby Mak
Sep 8 at 3:56
$gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
â Will Jagy
Sep 8 at 3:57
$gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
â Will Jagy
Sep 8 at 3:57
@WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
â Jason Kim
Sep 8 at 4:06
@WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
â Jason Kim
Sep 8 at 4:06
@JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
â Will Jagy
Sep 8 at 4:09
@JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
â Will Jagy
Sep 8 at 4:09
Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
â Jason Kim
Sep 8 at 4:17
Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
â Jason Kim
Sep 8 at 4:17
 |Â
show 1 more comment
4 Answers
4
active
oldest
votes
up vote
1
down vote
Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).
Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)
So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$
Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.
add a comment |Â
up vote
0
down vote
We work in the ring $R=Bbb Z/143$.
Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
$$
108=m^37 .
$$
We start from this, take the $13$.th power and get
$$
m=m^481=(m^37)^13=108^13=69
$$
in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
One checks that this is a solution, to have the converse too.
sage search for the solution:
sage: R = Zmod(143)
sage: for m in R:
....: if m^37 == R(108):
....: print m
....:
69
sage: R(108)^13
69
add a comment |Â
up vote
0
down vote
By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.
$varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.
Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)
Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)
add a comment |Â
up vote
0
down vote
As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$
Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$
$$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$
$108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem
Similarly, $(108)^13equiv4pmod13 (2)$
Apply Chinese Remainder Theorem, on $(1),(2)$
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).
Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)
So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$
Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.
add a comment |Â
up vote
1
down vote
Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).
Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)
So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$
Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).
Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)
So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$
Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.
Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).
Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)
So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$
Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.
edited Sep 8 at 4:12
answered Sep 8 at 4:07
P Vanchinathan
14.1k12036
14.1k12036
add a comment |Â
add a comment |Â
up vote
0
down vote
We work in the ring $R=Bbb Z/143$.
Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
$$
108=m^37 .
$$
We start from this, take the $13$.th power and get
$$
m=m^481=(m^37)^13=108^13=69
$$
in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
One checks that this is a solution, to have the converse too.
sage search for the solution:
sage: R = Zmod(143)
sage: for m in R:
....: if m^37 == R(108):
....: print m
....:
69
sage: R(108)^13
69
add a comment |Â
up vote
0
down vote
We work in the ring $R=Bbb Z/143$.
Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
$$
108=m^37 .
$$
We start from this, take the $13$.th power and get
$$
m=m^481=(m^37)^13=108^13=69
$$
in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
One checks that this is a solution, to have the converse too.
sage search for the solution:
sage: R = Zmod(143)
sage: for m in R:
....: if m^37 == R(108):
....: print m
....:
69
sage: R(108)^13
69
add a comment |Â
up vote
0
down vote
up vote
0
down vote
We work in the ring $R=Bbb Z/143$.
Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
$$
108=m^37 .
$$
We start from this, take the $13$.th power and get
$$
m=m^481=(m^37)^13=108^13=69
$$
in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
One checks that this is a solution, to have the converse too.
sage search for the solution:
sage: R = Zmod(143)
sage: for m in R:
....: if m^37 == R(108):
....: print m
....:
69
sage: R(108)^13
69
We work in the ring $R=Bbb Z/143$.
Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
$$
108=m^37 .
$$
We start from this, take the $13$.th power and get
$$
m=m^481=(m^37)^13=108^13=69
$$
in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
One checks that this is a solution, to have the converse too.
sage search for the solution:
sage: R = Zmod(143)
sage: for m in R:
....: if m^37 == R(108):
....: print m
....:
69
sage: R(108)^13
69
answered Sep 8 at 4:12
dan_fulea
5,0901312
5,0901312
add a comment |Â
add a comment |Â
up vote
0
down vote
By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.
$varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.
Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)
Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)
add a comment |Â
up vote
0
down vote
By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.
$varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.
Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)
Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)
add a comment |Â
up vote
0
down vote
up vote
0
down vote
By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.
$varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.
Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)
Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)
By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.
$varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.
Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)
Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)
answered Sep 8 at 6:39
Chris Custer
6,6192622
6,6192622
add a comment |Â
add a comment |Â
up vote
0
down vote
As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$
Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$
$$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$
$108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem
Similarly, $(108)^13equiv4pmod13 (2)$
Apply Chinese Remainder Theorem, on $(1),(2)$
add a comment |Â
up vote
0
down vote
As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$
Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$
$$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$
$108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem
Similarly, $(108)^13equiv4pmod13 (2)$
Apply Chinese Remainder Theorem, on $(1),(2)$
add a comment |Â
up vote
0
down vote
up vote
0
down vote
As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$
Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$
$$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$
$108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem
Similarly, $(108)^13equiv4pmod13 (2)$
Apply Chinese Remainder Theorem, on $(1),(2)$
As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$
Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$
$$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$
$108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem
Similarly, $(108)^13equiv4pmod13 (2)$
Apply Chinese Remainder Theorem, on $(1),(2)$
answered Sep 8 at 10:57
lab bhattacharjee
216k14153266
216k14153266
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2909253%2fhow-to-solve-108-m37-pmod-143%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
â Toby Mak
Sep 8 at 3:56
$gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
â Will Jagy
Sep 8 at 3:57
@WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
â Jason Kim
Sep 8 at 4:06
@JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
â Will Jagy
Sep 8 at 4:09
Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
â Jason Kim
Sep 8 at 4:17