Solving inverse of modulo
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
How can I solve for: $$5^-1 mod 3$$ ?
I am having hard time to understand how it is solve so please make it easy for me how it works.
modular-arithmetic euclidean-algorithm
edited Aug 21 at 8:30
drhab
87.8k541119
asked Aug 21 at 8:24
MMJM
225
add a comment |Â
up vote
0
down vote
favorite
How can I solve for: $$5^-1 mod 3$$ ?
I am having hard time to understand how it is solve so please make it easy for me how it works.
modular-arithmetic euclidean-algorithm
edited Aug 21 at 8:30
drhab
87.8k541119
asked Aug 21 at 8:24
MMJM
225
You don't have 5 in $Bbb Z_3$, I think.
– Vim
Aug 21 at 8:30
1
@Arthur I never made any distinction between $mathbb Z_3$ and $mathbb Z/3mathbb Z$. For me $5$ is in both cases an abbreviation of $[5]=[2]$. Further an element can have more than one notation. Let me add: this is the way I see it.
– drhab
Aug 21 at 8:36
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
How can I solve for: $$5^-1 mod 3$$ ?
I am having hard time to understand how it is solve so please make it easy for me how it works.
modular-arithmetic euclidean-algorithm
edited Aug 21 at 8:30
drhab
87.8k541119
asked Aug 21 at 8:24
MMJM
225
How can I solve for: $$5^-1 mod 3$$ ?
I am having hard time to understand how it is solve so please make it easy for me how it works.
modular-arithmetic euclidean-algorithm
edited Aug 21 at 8:30
drhab
87.8k541119
asked Aug 21 at 8:24
MMJM
225
edited Aug 21 at 8:30
drhab
87.8k541119
edited Aug 21 at 8:30
drhab
87.8k541119
edited Aug 21 at 8:30
drhab
87.8k541119
87.8k541119
asked Aug 21 at 8:24
MMJM
225
asked Aug 21 at 8:24
MMJM
225
asked Aug 21 at 8:24
MMJM
225
225
You don't have 5 in $Bbb Z_3$, I think.
– Vim
Aug 21 at 8:30
1
@Arthur I never made any distinction between $mathbb Z_3$ and $mathbb Z/3mathbb Z$. For me $5$ is in both cases an abbreviation of $[5]=[2]$. Further an element can have more than one notation. Let me add: this is the way I see it.
– drhab
Aug 21 at 8:36
add a comment |Â
You don't have 5 in $Bbb Z_3$, I think.
– Vim
Aug 21 at 8:30
1
@Arthur I never made any distinction between $mathbb Z_3$ and $mathbb Z/3mathbb Z$. For me $5$ is in both cases an abbreviation of $[5]=[2]$. Further an element can have more than one notation. Let me add: this is the way I see it.
– drhab
Aug 21 at 8:36
You don't have 5 in $Bbb Z_3$, I think.
– Vim
Aug 21 at 8:30
You don't have 5 in $Bbb Z_3$, I think.
– Vim
Aug 21 at 8:30
1
1
@Arthur I never made any distinction between $mathbb Z_3$ and $mathbb Z/3mathbb Z$. For me $5$ is in both cases an abbreviation of $[5]=[2]$. Further an element can have more than one notation. Let me add: this is the way I see it.
– drhab
Aug 21 at 8:36
@Arthur I never made any distinction between $mathbb Z_3$ and $mathbb Z/3mathbb Z$. For me $5$ is in both cases an abbreviation of $[5]=[2]$. Further an element can have more than one notation. Let me add: this is the way I see it.
– drhab
Aug 21 at 8:36
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
$5^-1$ is the number such that if you multiply by $5$, you get $1$. In other words, it's the solution to $5xequiv 1pmod 3$.
Modulo $3$, multiplying by $5$ is the same as multiplying by $2$, so $5^-1$ is the same as $2^-1$.
Now, what number (modulo $3$) is such that if you multiply by $2$, you get $1$? In other words, solve $2xequiv 1pmod 3$. There are only three different values that $x$ could have, so try them all, and you will find the answer.
There are ways of actually finding this $x$, in case we are working modulo $n$ and $n$ becomes too large to feasibly test every case. Specifically, the extended Euclidean algorithm will let you find $x$ in $O(log n)$ steps, assuming a solution exists (and if a solution doesn't exist then the algorithm will tell you that too).
answered Aug 21 at 8:30
Arthur
101k794176
For what it's worth: if $p$ is a prime then the inverse $a^-1$ always exists in $Bbb Z_p$ for each nonzero $a$.
– Vim
Aug 21 at 9:36
@Vim And if $n$ is not prime, but $gcd(a, n) = 1$, then $a^-1pmod n$ has multiple solutions. You're right, I should've mentioned that.
– Arthur
Aug 21 at 10:15
add a comment |Â
up vote
1
down vote
First note $5=2$. Then consider $2times ?=1$ where you can try $?$ from $0,1,2$. Not a tedious task.
answered Aug 21 at 8:31
Vim
7,84631244
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
$5^-1$ is the number such that if you multiply by $5$, you get $1$. In other words, it's the solution to $5xequiv 1pmod 3$.
Modulo $3$, multiplying by $5$ is the same as multiplying by $2$, so $5^-1$ is the same as $2^-1$.
Now, what number (modulo $3$) is such that if you multiply by $2$, you get $1$? In other words, solve $2xequiv 1pmod 3$. There are only three different values that $x$ could have, so try them all, and you will find the answer.
There are ways of actually finding this $x$, in case we are working modulo $n$ and $n$ becomes too large to feasibly test every case. Specifically, the extended Euclidean algorithm will let you find $x$ in $O(log n)$ steps, assuming a solution exists (and if a solution doesn't exist then the algorithm will tell you that too).
answered Aug 21 at 8:30
Arthur
101k794176
For what it's worth: if $p$ is a prime then the inverse $a^-1$ always exists in $Bbb Z_p$ for each nonzero $a$.
– Vim
Aug 21 at 9:36
@Vim And if $n$ is not prime, but $gcd(a, n) = 1$, then $a^-1pmod n$ has multiple solutions. You're right, I should've mentioned that.
– Arthur
Aug 21 at 10:15
add a comment |Â
up vote
3
down vote
accepted
$5^-1$ is the number such that if you multiply by $5$, you get $1$. In other words, it's the solution to $5xequiv 1pmod 3$.
Modulo $3$, multiplying by $5$ is the same as multiplying by $2$, so $5^-1$ is the same as $2^-1$.
Now, what number (modulo $3$) is such that if you multiply by $2$, you get $1$? In other words, solve $2xequiv 1pmod 3$. There are only three different values that $x$ could have, so try them all, and you will find the answer.
There are ways of actually finding this $x$, in case we are working modulo $n$ and $n$ becomes too large to feasibly test every case. Specifically, the extended Euclidean algorithm will let you find $x$ in $O(log n)$ steps, assuming a solution exists (and if a solution doesn't exist then the algorithm will tell you that too).
answered Aug 21 at 8:30
Arthur
101k794176
For what it's worth: if $p$ is a prime then the inverse $a^-1$ always exists in $Bbb Z_p$ for each nonzero $a$.
– Vim
Aug 21 at 9:36
@Vim And if $n$ is not prime, but $gcd(a, n) = 1$, then $a^-1pmod n$ has multiple solutions. You're right, I should've mentioned that.
– Arthur
Aug 21 at 10:15
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
$5^-1$ is the number such that if you multiply by $5$, you get $1$. In other words, it's the solution to $5xequiv 1pmod 3$.
Modulo $3$, multiplying by $5$ is the same as multiplying by $2$, so $5^-1$ is the same as $2^-1$.
Now, what number (modulo $3$) is such that if you multiply by $2$, you get $1$? In other words, solve $2xequiv 1pmod 3$. There are only three different values that $x$ could have, so try them all, and you will find the answer.
There are ways of actually finding this $x$, in case we are working modulo $n$ and $n$ becomes too large to feasibly test every case. Specifically, the extended Euclidean algorithm will let you find $x$ in $O(log n)$ steps, assuming a solution exists (and if a solution doesn't exist then the algorithm will tell you that too).
answered Aug 21 at 8:30
Arthur
101k794176
$5^-1$ is the number such that if you multiply by $5$, you get $1$. In other words, it's the solution to $5xequiv 1pmod 3$.
Modulo $3$, multiplying by $5$ is the same as multiplying by $2$, so $5^-1$ is the same as $2^-1$.
Now, what number (modulo $3$) is such that if you multiply by $2$, you get $1$? In other words, solve $2xequiv 1pmod 3$. There are only three different values that $x$ could have, so try them all, and you will find the answer.
There are ways of actually finding this $x$, in case we are working modulo $n$ and $n$ becomes too large to feasibly test every case. Specifically, the extended Euclidean algorithm will let you find $x$ in $O(log n)$ steps, assuming a solution exists (and if a solution doesn't exist then the algorithm will tell you that too).
answered Aug 21 at 8:30
Arthur
101k794176
edited Aug 21 at 8:40
answered Aug 21 at 8:30
Arthur
101k794176
answered Aug 21 at 8:30
Arthur
101k794176
answered Aug 21 at 8:30
Arthur
101k794176
101k794176
For what it's worth: if $p$ is a prime then the inverse $a^-1$ always exists in $Bbb Z_p$ for each nonzero $a$.
– Vim
Aug 21 at 9:36
@Vim And if $n$ is not prime, but $gcd(a, n) = 1$, then $a^-1pmod n$ has multiple solutions. You're right, I should've mentioned that.
– Arthur
Aug 21 at 10:15
add a comment |Â
For what it's worth: if $p$ is a prime then the inverse $a^-1$ always exists in $Bbb Z_p$ for each nonzero $a$.
– Vim
Aug 21 at 9:36
@Vim And if $n$ is not prime, but $gcd(a, n) = 1$, then $a^-1pmod n$ has multiple solutions. You're right, I should've mentioned that.
– Arthur
Aug 21 at 10:15
For what it's worth: if $p$ is a prime then the inverse $a^-1$ always exists in $Bbb Z_p$ for each nonzero $a$.
– Vim
Aug 21 at 9:36
For what it's worth: if $p$ is a prime then the inverse $a^-1$ always exists in $Bbb Z_p$ for each nonzero $a$.
– Vim
Aug 21 at 9:36
@Vim And if $n$ is not prime, but $gcd(a, n) = 1$, then $a^-1pmod n$ has multiple solutions. You're right, I should've mentioned that.
– Arthur
Aug 21 at 10:15
@Vim And if $n$ is not prime, but $gcd(a, n) = 1$, then $a^-1pmod n$ has multiple solutions. You're right, I should've mentioned that.
– Arthur
Aug 21 at 10:15
add a comment |Â
up vote
1
down vote
First note $5=2$. Then consider $2times ?=1$ where you can try $?$ from $0,1,2$. Not a tedious task.
answered Aug 21 at 8:31
Vim
7,84631244
add a comment |Â
up vote
1
down vote
First note $5=2$. Then consider $2times ?=1$ where you can try $?$ from $0,1,2$. Not a tedious task.
answered Aug 21 at 8:31
Vim
7,84631244
add a comment |Â
up vote
1
down vote
up vote
1
down vote
First note $5=2$. Then consider $2times ?=1$ where you can try $?$ from $0,1,2$. Not a tedious task.
answered Aug 21 at 8:31
Vim
7,84631244
First note $5=2$. Then consider $2times ?=1$ where you can try $?$ from $0,1,2$. Not a tedious task.
answered Aug 21 at 8:31
Vim
7,84631244
answered Aug 21 at 8:31
Vim
7,84631244
answered Aug 21 at 8:31
Vim
7,84631244
answered Aug 21 at 8:31
Vim
7,84631244
7,84631244
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%2f2889608%2fsolving-inverse-of-modulo%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
You don't have 5 in $Bbb Z_3$, I think.
– Vim
Aug 21 at 8:30
1
@Arthur I never made any distinction between $mathbb Z_3$ and $mathbb Z/3mathbb Z$. For me $5$ is in both cases an abbreviation of $[5]=[2]$. Further an element can have more than one notation. Let me add: this is the way I see it.
– drhab
Aug 21 at 8:36