Find inverse of $a mod p$ [closed]

Clash Royale CLAN TAG#URR8PPP

up vote
-1
down vote

favorite

If we want to find the inverse of $a$ mod $p$, $p$ not prime, then we can write
$$ax equiv 1 mod p$$
$$ax+pyequiv 1 mod p$$ and use the extended euclidean algorithm to solve for $x$, which is the inverse mod $p$

My Question
How do we find $x$ if $gcd(a,p)neq 1$

elementary-number-theory proof-writing

share|cite|improve this question

edited Jul 20 at 1:03

BDN

573417

asked Jul 19 at 23:52

john fowles

1,093817

closed as off-topic by Mostafa Ayaz, Taroccoesbrocco, choco_addicted, John B, Xander Henderson Jul 28 at 22:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Mostafa Ayaz, Taroccoesbrocco, choco_addicted, John B, Xander Henderson

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  if gcd(a,p)≠1 ...then there are no solutions (why?).
  – dxiv
  Jul 19 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is it because bezouts identity tells us that $ax+pyequiv r text mod p$, such that $r$ is a multiple of gcd$(a,p)$?
  – john fowles
  Jul 20 at 0:07
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  More directly, $,ax equiv n pmod p implies ax = kp + n implies d = gcd(a,p) mid n,$. Just write $,a = a'd,$, $,p=p'd,$, then $,n = ax - kp = d cdot (a'x-kp'),$.
  – dxiv
  Jul 20 at 0:12
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The modular inverse of $a mod m$ exists if and only if $gcd(a, m) = 1$
  – feynhat
  Jul 20 at 4:35
  
  

  
  
  
  

add a comment | 

up vote
-1
down vote

favorite

If we want to find the inverse of $a$ mod $p$, $p$ not prime, then we can write
$$ax equiv 1 mod p$$
$$ax+pyequiv 1 mod p$$ and use the extended euclidean algorithm to solve for $x$, which is the inverse mod $p$

My Question
How do we find $x$ if $gcd(a,p)neq 1$

elementary-number-theory proof-writing

share|cite|improve this question

edited Jul 20 at 1:03

BDN

573417

asked Jul 19 at 23:52

john fowles

1,093817

closed as off-topic by Mostafa Ayaz, Taroccoesbrocco, choco_addicted, John B, Xander Henderson Jul 28 at 22:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Mostafa Ayaz, Taroccoesbrocco, choco_addicted, John B, Xander Henderson

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  if gcd(a,p)≠1 ...then there are no solutions (why?).
  – dxiv
  Jul 19 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is it because bezouts identity tells us that $ax+pyequiv r text mod p$, such that $r$ is a multiple of gcd$(a,p)$?
  – john fowles
  Jul 20 at 0:07
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  More directly, $,ax equiv n pmod p implies ax = kp + n implies d = gcd(a,p) mid n,$. Just write $,a = a'd,$, $,p=p'd,$, then $,n = ax - kp = d cdot (a'x-kp'),$.
  – dxiv
  Jul 20 at 0:12
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The modular inverse of $a mod m$ exists if and only if $gcd(a, m) = 1$
  – feynhat
  Jul 20 at 4:35
  
  

  
  
  
  

add a comment | 

up vote
-1
down vote

favorite

up vote
-1
down vote

favorite

If we want to find the inverse of $a$ mod $p$, $p$ not prime, then we can write
$$ax equiv 1 mod p$$
$$ax+pyequiv 1 mod p$$ and use the extended euclidean algorithm to solve for $x$, which is the inverse mod $p$

My Question
How do we find $x$ if $gcd(a,p)neq 1$

elementary-number-theory proof-writing

share|cite|improve this question

edited Jul 20 at 1:03

BDN

573417

asked Jul 19 at 23:52

john fowles

1,093817

If we want to find the inverse of $a$ mod $p$, $p$ not prime, then we can write
$$ax equiv 1 mod p$$
$$ax+pyequiv 1 mod p$$ and use the extended euclidean algorithm to solve for $x$, which is the inverse mod $p$

My Question
How do we find $x$ if $gcd(a,p)neq 1$

elementary-number-theory proof-writing

share|cite|improve this question

edited Jul 20 at 1:03

BDN

573417

asked Jul 19 at 23:52

john fowles

1,093817

share|cite|improve this question

share|cite|improve this question

edited Jul 20 at 1:03

BDN

573417

edited Jul 20 at 1:03

BDN

573417

edited Jul 20 at 1:03

BDN

573417

573417

asked Jul 19 at 23:52

john fowles

1,093817

asked Jul 19 at 23:52

john fowles

1,093817

asked Jul 19 at 23:52

john fowles

1,093817

1,093817

closed as off-topic by Mostafa Ayaz, Taroccoesbrocco, choco_addicted, John B, Xander Henderson Jul 28 at 22:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Mostafa Ayaz, Taroccoesbrocco, choco_addicted, John B, Xander Henderson

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by Mostafa Ayaz, Taroccoesbrocco, choco_addicted, John B, Xander Henderson Jul 28 at 22:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Mostafa Ayaz, Taroccoesbrocco, choco_addicted, John B, Xander Henderson

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  if gcd(a,p)≠1 ...then there are no solutions (why?).
  – dxiv
  Jul 19 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is it because bezouts identity tells us that $ax+pyequiv r text mod p$, such that $r$ is a multiple of gcd$(a,p)$?
  – john fowles
  Jul 20 at 0:07
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  More directly, $,ax equiv n pmod p implies ax = kp + n implies d = gcd(a,p) mid n,$. Just write $,a = a'd,$, $,p=p'd,$, then $,n = ax - kp = d cdot (a'x-kp'),$.
  – dxiv
  Jul 20 at 0:12
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The modular inverse of $a mod m$ exists if and only if $gcd(a, m) = 1$
  – feynhat
  Jul 20 at 4:35
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  if gcd(a,p)≠1 ...then there are no solutions (why?).
  – dxiv
  Jul 19 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is it because bezouts identity tells us that $ax+pyequiv r text mod p$, such that $r$ is a multiple of gcd$(a,p)$?
  – john fowles
  Jul 20 at 0:07
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  More directly, $,ax equiv n pmod p implies ax = kp + n implies d = gcd(a,p) mid n,$. Just write $,a = a'd,$, $,p=p'd,$, then $,n = ax - kp = d cdot (a'x-kp'),$.
  – dxiv
  Jul 20 at 0:12
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The modular inverse of $a mod m$ exists if and only if $gcd(a, m) = 1$
  – feynhat
  Jul 20 at 4:35
  
  

  
  
  
  

5

5

if gcd(a,p)≠1 ...then there are no solutions (why?).
– dxiv
Jul 19 at 23:55

if gcd(a,p)≠1 ...then there are no solutions (why?).
– dxiv
Jul 19 at 23:55

Is it because bezouts identity tells us that $ax+pyequiv r text mod p$, such that $r$ is a multiple of gcd$(a,p)$?
– john fowles
Jul 20 at 0:07

Is it because bezouts identity tells us that $ax+pyequiv r text mod p$, such that $r$ is a multiple of gcd$(a,p)$?
– john fowles
Jul 20 at 0:07

1

1

More directly, $,ax equiv n pmod p implies ax = kp + n implies d = gcd(a,p) mid n,$. Just write $,a = a'd,$, $,p=p'd,$, then $,n = ax - kp = d cdot (a'x-kp'),$.
– dxiv
Jul 20 at 0:12

More directly, $,ax equiv n pmod p implies ax = kp + n implies d = gcd(a,p) mid n,$. Just write $,a = a'd,$, $,p=p'd,$, then $,n = ax - kp = d cdot (a'x-kp'),$.
– dxiv
Jul 20 at 0:12

The modular inverse of $a mod m$ exists if and only if $gcd(a, m) = 1$
– feynhat
Jul 20 at 4:35

The modular inverse of $a mod m$ exists if and only if $gcd(a, m) = 1$
– feynhat
Jul 20 at 4:35

add a comment | 

2 Answers
2

active

oldest

votes

up vote
1
down vote



accepted

We are in the situation where $a$ and $p$ are both multiples of some $d>1$.

Two numbers which are multiples of same $d$ (by positive or negative integers it is immaterial) will differ by at least $d$.

Getting an inverse for $a$ mod $p$ means finding $x,y $ such that $ax - (-yp)=1$.
As both $ax$ and $-yp$ are multiples of $d$ the difference of $1$ is not possible to achieve (as $d>1$ by hypothesis). Hence inverse does not exist.

share|cite|improve this answer

answered Jul 20 at 0:29

P Vanchinathan

13.9k12035

add a comment | 

up vote
2
down vote

$ax+py=1$ must be true for some integer $y$... but this means $gcd (a,p)=1$

share|cite|improve this answer

answered Jul 20 at 0:12

Chris Custer

5,4482622

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So gcd$(a,p)=1$ follows because if $ax+py=1$ where gcd$(a,p)neq 1$ then we could factor some multiple $k in mathbbN_+$ out of $ax+py=1 Longrightarrow k(a'x+p'y)=1$ which can't hold since $k(a'x+p'y) > 1$? Is this correct?
  – john fowles
  Jul 20 at 0:24
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Whenever $ax+py=1$ then, for a common divisor, $d$, since $d$ divides the LHS, it follows that $d$ divides $1$...
  – Chris Custer
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This makes sense. Thanks
  – john fowles
  Jul 20 at 1:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  See @dxiv's second comment under your question for the general rule...
  – Chris Custer
  Jul 20 at 1:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This is an example of a linear diophantine equation...
  – Chris Custer
  Jul 20 at 1:21
  

  
  
  
  

add a comment | 

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote



accepted

We are in the situation where $a$ and $p$ are both multiples of some $d>1$.

Two numbers which are multiples of same $d$ (by positive or negative integers it is immaterial) will differ by at least $d$.

Getting an inverse for $a$ mod $p$ means finding $x,y $ such that $ax - (-yp)=1$.
As both $ax$ and $-yp$ are multiples of $d$ the difference of $1$ is not possible to achieve (as $d>1$ by hypothesis). Hence inverse does not exist.

share|cite|improve this answer

answered Jul 20 at 0:29

P Vanchinathan

13.9k12035

add a comment | 

up vote
1
down vote



accepted

We are in the situation where $a$ and $p$ are both multiples of some $d>1$.

Two numbers which are multiples of same $d$ (by positive or negative integers it is immaterial) will differ by at least $d$.

Getting an inverse for $a$ mod $p$ means finding $x,y $ such that $ax - (-yp)=1$.
As both $ax$ and $-yp$ are multiples of $d$ the difference of $1$ is not possible to achieve (as $d>1$ by hypothesis). Hence inverse does not exist.

share|cite|improve this answer

answered Jul 20 at 0:29

P Vanchinathan

13.9k12035

add a comment | 

up vote
1
down vote



accepted

up vote
1
down vote



accepted

We are in the situation where $a$ and $p$ are both multiples of some $d>1$.

Two numbers which are multiples of same $d$ (by positive or negative integers it is immaterial) will differ by at least $d$.

Getting an inverse for $a$ mod $p$ means finding $x,y $ such that $ax - (-yp)=1$.
As both $ax$ and $-yp$ are multiples of $d$ the difference of $1$ is not possible to achieve (as $d>1$ by hypothesis). Hence inverse does not exist.

share|cite|improve this answer

answered Jul 20 at 0:29

P Vanchinathan

13.9k12035

We are in the situation where $a$ and $p$ are both multiples of some $d>1$.

Two numbers which are multiples of same $d$ (by positive or negative integers it is immaterial) will differ by at least $d$.

Getting an inverse for $a$ mod $p$ means finding $x,y $ such that $ax - (-yp)=1$.
As both $ax$ and $-yp$ are multiples of $d$ the difference of $1$ is not possible to achieve (as $d>1$ by hypothesis). Hence inverse does not exist.

share|cite|improve this answer

answered Jul 20 at 0:29

P Vanchinathan

13.9k12035

share|cite|improve this answer

share|cite|improve this answer

answered Jul 20 at 0:29

P Vanchinathan

13.9k12035

answered Jul 20 at 0:29

P Vanchinathan

13.9k12035

answered Jul 20 at 0:29

P Vanchinathan

13.9k12035

13.9k12035

add a comment | 

add a comment | 

up vote
2
down vote

$ax+py=1$ must be true for some integer $y$... but this means $gcd (a,p)=1$

share|cite|improve this answer

answered Jul 20 at 0:12

Chris Custer

5,4482622

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So gcd$(a,p)=1$ follows because if $ax+py=1$ where gcd$(a,p)neq 1$ then we could factor some multiple $k in mathbbN_+$ out of $ax+py=1 Longrightarrow k(a'x+p'y)=1$ which can't hold since $k(a'x+p'y) > 1$? Is this correct?
  – john fowles
  Jul 20 at 0:24
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Whenever $ax+py=1$ then, for a common divisor, $d$, since $d$ divides the LHS, it follows that $d$ divides $1$...
  – Chris Custer
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This makes sense. Thanks
  – john fowles
  Jul 20 at 1:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  See @dxiv's second comment under your question for the general rule...
  – Chris Custer
  Jul 20 at 1:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This is an example of a linear diophantine equation...
  – Chris Custer
  Jul 20 at 1:21
  

  
  
  
  

add a comment | 

up vote
2
down vote

$ax+py=1$ must be true for some integer $y$... but this means $gcd (a,p)=1$

share|cite|improve this answer

answered Jul 20 at 0:12

Chris Custer

5,4482622

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So gcd$(a,p)=1$ follows because if $ax+py=1$ where gcd$(a,p)neq 1$ then we could factor some multiple $k in mathbbN_+$ out of $ax+py=1 Longrightarrow k(a'x+p'y)=1$ which can't hold since $k(a'x+p'y) > 1$? Is this correct?
  – john fowles
  Jul 20 at 0:24
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Whenever $ax+py=1$ then, for a common divisor, $d$, since $d$ divides the LHS, it follows that $d$ divides $1$...
  – Chris Custer
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This makes sense. Thanks
  – john fowles
  Jul 20 at 1:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  See @dxiv's second comment under your question for the general rule...
  – Chris Custer
  Jul 20 at 1:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This is an example of a linear diophantine equation...
  – Chris Custer
  Jul 20 at 1:21
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

$ax+py=1$ must be true for some integer $y$... but this means $gcd (a,p)=1$

share|cite|improve this answer

answered Jul 20 at 0:12

Chris Custer

5,4482622

$ax+py=1$ must be true for some integer $y$... but this means $gcd (a,p)=1$

share|cite|improve this answer

answered Jul 20 at 0:12

Chris Custer

5,4482622

share|cite|improve this answer

share|cite|improve this answer

answered Jul 20 at 0:12

Chris Custer

5,4482622

answered Jul 20 at 0:12

Chris Custer

5,4482622

answered Jul 20 at 0:12

Chris Custer

5,4482622

5,4482622

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So gcd$(a,p)=1$ follows because if $ax+py=1$ where gcd$(a,p)neq 1$ then we could factor some multiple $k in mathbbN_+$ out of $ax+py=1 Longrightarrow k(a'x+p'y)=1$ which can't hold since $k(a'x+p'y) > 1$? Is this correct?
  – john fowles
  Jul 20 at 0:24
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Whenever $ax+py=1$ then, for a common divisor, $d$, since $d$ divides the LHS, it follows that $d$ divides $1$...
  – Chris Custer
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This makes sense. Thanks
  – john fowles
  Jul 20 at 1:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  See @dxiv's second comment under your question for the general rule...
  – Chris Custer
  Jul 20 at 1:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This is an example of a linear diophantine equation...
  – Chris Custer
  Jul 20 at 1:21
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So gcd$(a,p)=1$ follows because if $ax+py=1$ where gcd$(a,p)neq 1$ then we could factor some multiple $k in mathbbN_+$ out of $ax+py=1 Longrightarrow k(a'x+p'y)=1$ which can't hold since $k(a'x+p'y) > 1$? Is this correct?
  – john fowles
  Jul 20 at 0:24
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Whenever $ax+py=1$ then, for a common divisor, $d$, since $d$ divides the LHS, it follows that $d$ divides $1$...
  – Chris Custer
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This makes sense. Thanks
  – john fowles
  Jul 20 at 1:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  See @dxiv's second comment under your question for the general rule...
  – Chris Custer
  Jul 20 at 1:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This is an example of a linear diophantine equation...
  – Chris Custer
  Jul 20 at 1:21
  

  
  
  
  

So gcd$(a,p)=1$ follows because if $ax+py=1$ where gcd$(a,p)neq 1$ then we could factor some multiple $k in mathbbN_+$ out of $ax+py=1 Longrightarrow k(a'x+p'y)=1$ which can't hold since $k(a'x+p'y) > 1$? Is this correct?
– john fowles
Jul 20 at 0:24

So gcd$(a,p)=1$ follows because if $ax+py=1$ where gcd$(a,p)neq 1$ then we could factor some multiple $k in mathbbN_+$ out of $ax+py=1 Longrightarrow k(a'x+p'y)=1$ which can't hold since $k(a'x+p'y) > 1$? Is this correct?
– john fowles
Jul 20 at 0:24

1

1

Whenever $ax+py=1$ then, for a common divisor, $d$, since $d$ divides the LHS, it follows that $d$ divides $1$...
– Chris Custer
Jul 20 at 0:39

Whenever $ax+py=1$ then, for a common divisor, $d$, since $d$ divides the LHS, it follows that $d$ divides $1$...
– Chris Custer
Jul 20 at 0:39

This makes sense. Thanks
– john fowles
Jul 20 at 1:04

This makes sense. Thanks
– john fowles
Jul 20 at 1:04

See @dxiv's second comment under your question for the general rule...
– Chris Custer
Jul 20 at 1:14

See @dxiv's second comment under your question for the general rule...
– Chris Custer
Jul 20 at 1:14

This is an example of a linear diophantine equation...
– Chris Custer
Jul 20 at 1:21

This is an example of a linear diophantine equation...
– Chris Custer
Jul 20 at 1:21

add a comment |