Mixing
Number of solutions to a linear congruence equation
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Consider
$$ ax equiv c mod m $$
If there is a solution, prove that there are exactly $gcd(a, m)$ distinct solutions modulo $m$.
I can prove that there are at least that many, because if $x_0 < m$ is a solution, $x=x_0 + frack cdot mgcd(a,m)$ for any $kin mathbbZ$ is also a solution. Thus there are $gcd(a, m)$ solutions modulo $m$ for $0 le k le gcd(a,m)-1$.
But how can I prove these are the only solutions, i.e. there is no solution of other forms?
elementary-number-theory modular-arithmetic
asked Aug 1 at 20:35
qweruiop
19110
add a comment |Â
up vote
1
down vote
favorite
Consider
$$ ax equiv c mod m $$
If there is a solution, prove that there are exactly $gcd(a, m)$ distinct solutions modulo $m$.
I can prove that there are at least that many, because if $x_0 < m$ is a solution, $x=x_0 + frack cdot mgcd(a,m)$ for any $kin mathbbZ$ is also a solution. Thus there are $gcd(a, m)$ solutions modulo $m$ for $0 le k le gcd(a,m)-1$.
But how can I prove these are the only solutions, i.e. there is no solution of other forms?
elementary-number-theory modular-arithmetic
asked Aug 1 at 20:35
qweruiop
19110
If $x_0+z$, where $znedfrack cdot mgcd(a,m)$ then $az=0$ so.....?
– Piquito
Aug 1 at 21:01
So $z propto fracmdiv(a)$ and since $zin mathbbZ$, it must be $z propto fracmcd(a, m)$. Since $cd(a,m) mid gcd(a,m)$, $z propto fracmgcd(a, m)$... Is that the reasoning
– qweruiop
Aug 1 at 23:51
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Consider
$$ ax equiv c mod m $$
If there is a solution, prove that there are exactly $gcd(a, m)$ distinct solutions modulo $m$.
I can prove that there are at least that many, because if $x_0 < m$ is a solution, $x=x_0 + frack cdot mgcd(a,m)$ for any $kin mathbbZ$ is also a solution. Thus there are $gcd(a, m)$ solutions modulo $m$ for $0 le k le gcd(a,m)-1$.
But how can I prove these are the only solutions, i.e. there is no solution of other forms?
elementary-number-theory modular-arithmetic
asked Aug 1 at 20:35
qweruiop
19110
Consider
$$ ax equiv c mod m $$
If there is a solution, prove that there are exactly $gcd(a, m)$ distinct solutions modulo $m$.
I can prove that there are at least that many, because if $x_0 < m$ is a solution, $x=x_0 + frack cdot mgcd(a,m)$ for any $kin mathbbZ$ is also a solution. Thus there are $gcd(a, m)$ solutions modulo $m$ for $0 le k le gcd(a,m)-1$.
But how can I prove these are the only solutions, i.e. there is no solution of other forms?
elementary-number-theory modular-arithmetic
asked Aug 1 at 20:35
qweruiop
19110
edited Aug 2 at 0:47
asked Aug 1 at 20:35
qweruiop
19110
asked Aug 1 at 20:35
qweruiop
19110
asked Aug 1 at 20:35
qweruiop
19110
19110
If $x_0+z$, where $znedfrack cdot mgcd(a,m)$ then $az=0$ so.....?
– Piquito
Aug 1 at 21:01
So $z propto fracmdiv(a)$ and since $zin mathbbZ$, it must be $z propto fracmcd(a, m)$. Since $cd(a,m) mid gcd(a,m)$, $z propto fracmgcd(a, m)$... Is that the reasoning
– qweruiop
Aug 1 at 23:51
add a comment |Â
If $x_0+z$, where $znedfrack cdot mgcd(a,m)$ then $az=0$ so.....?
– Piquito
Aug 1 at 21:01
So $z propto fracmdiv(a)$ and since $zin mathbbZ$, it must be $z propto fracmcd(a, m)$. Since $cd(a,m) mid gcd(a,m)$, $z propto fracmgcd(a, m)$... Is that the reasoning
– qweruiop
Aug 1 at 23:51
If $x_0+z$, where $znedfrack cdot mgcd(a,m)$ then $az=0$ so.....?
– Piquito
Aug 1 at 21:01
If $x_0+z$, where $znedfrack cdot mgcd(a,m)$ then $az=0$ so.....?
– Piquito
Aug 1 at 21:01
So $z propto fracmdiv(a)$ and since $zin mathbbZ$, it must be $z propto fracmcd(a, m)$. Since $cd(a,m) mid gcd(a,m)$, $z propto fracmgcd(a, m)$... Is that the reasoning
– qweruiop
Aug 1 at 23:51
So $z propto fracmdiv(a)$ and since $zin mathbbZ$, it must be $z propto fracmcd(a, m)$. Since $cd(a,m) mid gcd(a,m)$, $z propto fracmgcd(a, m)$... Is that the reasoning
– qweruiop
Aug 1 at 23:51
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
$$axequiv cpmodmtag1$$
First consider $gcd(a,m)=1$. Then when $x$ runs through a complete residue system modulo $m$, so does $ax$. Hence $ax$ is congruent to $c$ for one and only one value of $x$ from the complete residue system. So there is just one solution to the congruence $(1)$ when $gcd(a,m)=1$.
Now let $gcd(a,m)=d>1$. For any solution to $(1)$ we need $dmid c$, otherwise there are no solutions. (To see this write $ax=c+mr$, then since this is equivalent to $a_0dx=c+m_0dr$ we must have $c=c_0d$.)
If $dmid c$ then we can rewrite $(1)$ as
$$a_0dxequiv c_0dpmodm_0d$$
which on dividing through by $d$ gives the equivalent congruence to $(1)$:
$$a_0xequiv c_0pmodm_0tag2$$
where $gcd(a_0,m_0)=1$, meaning $(2)$ will have one solution modulo $m_0$.
Now if $x_0$ is the least nonnegative residue of $(2)$, then each $x$ that is a solution to $(2)$ satisfies
$$xequiv x_0pmodm_0tag3$$
But modulo $m$ we must look at where the least nonnegative residues from $0$, $1$, $2,dotsc,m-1$ appear as solutions to $(3)$, this then gives us $d$ solutions of $(2)$:
$$x_0,, x_0+m_0,, x_0+2m_0,, dotsc, x_0+(d-1)m_1$$
and these are all the possible $d$ amount of solutions of $(1)$.
To get it into the form you have, just note $m=m_0d$ so $m_0=fracmd=fracmgcd(a,m)$
$$x_0,, x_0+fracmgcd(a,m),, x_0+frac2mgcd(a,m),, dotsc, x_0+frac(d-1)mgcd(a,m)$$
answered Aug 1 at 23:52
Daniel Buck
2,2641623
(1) has a unique solution is the piece I've been missing. "Then when $x$ runs through a complete residue system modulo $m$, so does $ax$." -- Is this stated as a proposition somewhere?
– qweruiop
Aug 2 at 0:08
Yes, $a$ is a constant, so when $x$ runs through a complete residue system modulo $m$, it takes each of the $m$ values, $0,1,2,dotsc,m-1$, then $ax$ also does but unless $a=1$ these will be in some different order than $0,1,2,dotsc,m-1$.
– Daniel Buck
Aug 2 at 0:16
If $a=2$ and $m=5$, say then $ax$ takes the values $2cdot0,2cdot1,2cdot2,2cdot3,2cdot4$ which we take modulo $5$ to give $0,2,4,1,3$.
– Daniel Buck
Aug 2 at 0:23
Here is another way to show the uniqueness: suppose $x_1$ and $x_2$ are two solutions to (1), we have $a(x_1 - x_2) equiv 0 mod m$. Since $gcd(a,m)=1$, $a^-1$ exists so multiplying $a^-1$ on both sides we get $x_1 equiv x_2 mod m$.
– qweruiop
Aug 2 at 0:39
Yes, that works. Now see if you can extend on that if $gcd(a,m)>1$.
– Daniel Buck
Aug 2 at 0:45
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
$$axequiv cpmodmtag1$$
First consider $gcd(a,m)=1$. Then when $x$ runs through a complete residue system modulo $m$, so does $ax$. Hence $ax$ is congruent to $c$ for one and only one value of $x$ from the complete residue system. So there is just one solution to the congruence $(1)$ when $gcd(a,m)=1$.
Now let $gcd(a,m)=d>1$. For any solution to $(1)$ we need $dmid c$, otherwise there are no solutions. (To see this write $ax=c+mr$, then since this is equivalent to $a_0dx=c+m_0dr$ we must have $c=c_0d$.)
If $dmid c$ then we can rewrite $(1)$ as
$$a_0dxequiv c_0dpmodm_0d$$
which on dividing through by $d$ gives the equivalent congruence to $(1)$:
$$a_0xequiv c_0pmodm_0tag2$$
where $gcd(a_0,m_0)=1$, meaning $(2)$ will have one solution modulo $m_0$.
Now if $x_0$ is the least nonnegative residue of $(2)$, then each $x$ that is a solution to $(2)$ satisfies
$$xequiv x_0pmodm_0tag3$$
But modulo $m$ we must look at where the least nonnegative residues from $0$, $1$, $2,dotsc,m-1$ appear as solutions to $(3)$, this then gives us $d$ solutions of $(2)$:
$$x_0,, x_0+m_0,, x_0+2m_0,, dotsc, x_0+(d-1)m_1$$
and these are all the possible $d$ amount of solutions of $(1)$.
To get it into the form you have, just note $m=m_0d$ so $m_0=fracmd=fracmgcd(a,m)$
$$x_0,, x_0+fracmgcd(a,m),, x_0+frac2mgcd(a,m),, dotsc, x_0+frac(d-1)mgcd(a,m)$$
answered Aug 1 at 23:52
Daniel Buck
2,2641623
(1) has a unique solution is the piece I've been missing. "Then when $x$ runs through a complete residue system modulo $m$, so does $ax$." -- Is this stated as a proposition somewhere?
– qweruiop
Aug 2 at 0:08
Yes, $a$ is a constant, so when $x$ runs through a complete residue system modulo $m$, it takes each of the $m$ values, $0,1,2,dotsc,m-1$, then $ax$ also does but unless $a=1$ these will be in some different order than $0,1,2,dotsc,m-1$.
– Daniel Buck
Aug 2 at 0:16
If $a=2$ and $m=5$, say then $ax$ takes the values $2cdot0,2cdot1,2cdot2,2cdot3,2cdot4$ which we take modulo $5$ to give $0,2,4,1,3$.
– Daniel Buck
Aug 2 at 0:23
Here is another way to show the uniqueness: suppose $x_1$ and $x_2$ are two solutions to (1), we have $a(x_1 - x_2) equiv 0 mod m$. Since $gcd(a,m)=1$, $a^-1$ exists so multiplying $a^-1$ on both sides we get $x_1 equiv x_2 mod m$.
– qweruiop
Aug 2 at 0:39
Yes, that works. Now see if you can extend on that if $gcd(a,m)>1$.
– Daniel Buck
Aug 2 at 0:45
add a comment |Â
up vote
2
down vote
accepted
$$axequiv cpmodmtag1$$
First consider $gcd(a,m)=1$. Then when $x$ runs through a complete residue system modulo $m$, so does $ax$. Hence $ax$ is congruent to $c$ for one and only one value of $x$ from the complete residue system. So there is just one solution to the congruence $(1)$ when $gcd(a,m)=1$.
Now let $gcd(a,m)=d>1$. For any solution to $(1)$ we need $dmid c$, otherwise there are no solutions. (To see this write $ax=c+mr$, then since this is equivalent to $a_0dx=c+m_0dr$ we must have $c=c_0d$.)
If $dmid c$ then we can rewrite $(1)$ as
$$a_0dxequiv c_0dpmodm_0d$$
which on dividing through by $d$ gives the equivalent congruence to $(1)$:
$$a_0xequiv c_0pmodm_0tag2$$
where $gcd(a_0,m_0)=1$, meaning $(2)$ will have one solution modulo $m_0$.
Now if $x_0$ is the least nonnegative residue of $(2)$, then each $x$ that is a solution to $(2)$ satisfies
$$xequiv x_0pmodm_0tag3$$
But modulo $m$ we must look at where the least nonnegative residues from $0$, $1$, $2,dotsc,m-1$ appear as solutions to $(3)$, this then gives us $d$ solutions of $(2)$:
$$x_0,, x_0+m_0,, x_0+2m_0,, dotsc, x_0+(d-1)m_1$$
and these are all the possible $d$ amount of solutions of $(1)$.
To get it into the form you have, just note $m=m_0d$ so $m_0=fracmd=fracmgcd(a,m)$
$$x_0,, x_0+fracmgcd(a,m),, x_0+frac2mgcd(a,m),, dotsc, x_0+frac(d-1)mgcd(a,m)$$
answered Aug 1 at 23:52
Daniel Buck
2,2641623
(1) has a unique solution is the piece I've been missing. "Then when $x$ runs through a complete residue system modulo $m$, so does $ax$." -- Is this stated as a proposition somewhere?
– qweruiop
Aug 2 at 0:08
Yes, $a$ is a constant, so when $x$ runs through a complete residue system modulo $m$, it takes each of the $m$ values, $0,1,2,dotsc,m-1$, then $ax$ also does but unless $a=1$ these will be in some different order than $0,1,2,dotsc,m-1$.
– Daniel Buck
Aug 2 at 0:16
If $a=2$ and $m=5$, say then $ax$ takes the values $2cdot0,2cdot1,2cdot2,2cdot3,2cdot4$ which we take modulo $5$ to give $0,2,4,1,3$.
– Daniel Buck
Aug 2 at 0:23
Here is another way to show the uniqueness: suppose $x_1$ and $x_2$ are two solutions to (1), we have $a(x_1 - x_2) equiv 0 mod m$. Since $gcd(a,m)=1$, $a^-1$ exists so multiplying $a^-1$ on both sides we get $x_1 equiv x_2 mod m$.
– qweruiop
Aug 2 at 0:39
Yes, that works. Now see if you can extend on that if $gcd(a,m)>1$.
– Daniel Buck
Aug 2 at 0:45
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
$$axequiv cpmodmtag1$$
First consider $gcd(a,m)=1$. Then when $x$ runs through a complete residue system modulo $m$, so does $ax$. Hence $ax$ is congruent to $c$ for one and only one value of $x$ from the complete residue system. So there is just one solution to the congruence $(1)$ when $gcd(a,m)=1$.
Now let $gcd(a,m)=d>1$. For any solution to $(1)$ we need $dmid c$, otherwise there are no solutions. (To see this write $ax=c+mr$, then since this is equivalent to $a_0dx=c+m_0dr$ we must have $c=c_0d$.)
If $dmid c$ then we can rewrite $(1)$ as
$$a_0dxequiv c_0dpmodm_0d$$
which on dividing through by $d$ gives the equivalent congruence to $(1)$:
$$a_0xequiv c_0pmodm_0tag2$$
where $gcd(a_0,m_0)=1$, meaning $(2)$ will have one solution modulo $m_0$.
Now if $x_0$ is the least nonnegative residue of $(2)$, then each $x$ that is a solution to $(2)$ satisfies
$$xequiv x_0pmodm_0tag3$$
But modulo $m$ we must look at where the least nonnegative residues from $0$, $1$, $2,dotsc,m-1$ appear as solutions to $(3)$, this then gives us $d$ solutions of $(2)$:
$$x_0,, x_0+m_0,, x_0+2m_0,, dotsc, x_0+(d-1)m_1$$
and these are all the possible $d$ amount of solutions of $(1)$.
To get it into the form you have, just note $m=m_0d$ so $m_0=fracmd=fracmgcd(a,m)$
$$x_0,, x_0+fracmgcd(a,m),, x_0+frac2mgcd(a,m),, dotsc, x_0+frac(d-1)mgcd(a,m)$$
answered Aug 1 at 23:52
Daniel Buck
2,2641623
$$axequiv cpmodmtag1$$
First consider $gcd(a,m)=1$. Then when $x$ runs through a complete residue system modulo $m$, so does $ax$. Hence $ax$ is congruent to $c$ for one and only one value of $x$ from the complete residue system. So there is just one solution to the congruence $(1)$ when $gcd(a,m)=1$.
Now let $gcd(a,m)=d>1$. For any solution to $(1)$ we need $dmid c$, otherwise there are no solutions. (To see this write $ax=c+mr$, then since this is equivalent to $a_0dx=c+m_0dr$ we must have $c=c_0d$.)
If $dmid c$ then we can rewrite $(1)$ as
$$a_0dxequiv c_0dpmodm_0d$$
which on dividing through by $d$ gives the equivalent congruence to $(1)$:
$$a_0xequiv c_0pmodm_0tag2$$
where $gcd(a_0,m_0)=1$, meaning $(2)$ will have one solution modulo $m_0$.
Now if $x_0$ is the least nonnegative residue of $(2)$, then each $x$ that is a solution to $(2)$ satisfies
$$xequiv x_0pmodm_0tag3$$
But modulo $m$ we must look at where the least nonnegative residues from $0$, $1$, $2,dotsc,m-1$ appear as solutions to $(3)$, this then gives us $d$ solutions of $(2)$:
$$x_0,, x_0+m_0,, x_0+2m_0,, dotsc, x_0+(d-1)m_1$$
and these are all the possible $d$ amount of solutions of $(1)$.
To get it into the form you have, just note $m=m_0d$ so $m_0=fracmd=fracmgcd(a,m)$
$$x_0,, x_0+fracmgcd(a,m),, x_0+frac2mgcd(a,m),, dotsc, x_0+frac(d-1)mgcd(a,m)$$
answered Aug 1 at 23:52
Daniel Buck
2,2641623
edited Aug 2 at 0:23
answered Aug 1 at 23:52
Daniel Buck
2,2641623
answered Aug 1 at 23:52
Daniel Buck
2,2641623
answered Aug 1 at 23:52
Daniel Buck
2,2641623
2,2641623
(1) has a unique solution is the piece I've been missing. "Then when $x$ runs through a complete residue system modulo $m$, so does $ax$." -- Is this stated as a proposition somewhere?
– qweruiop
Aug 2 at 0:08
Yes, $a$ is a constant, so when $x$ runs through a complete residue system modulo $m$, it takes each of the $m$ values, $0,1,2,dotsc,m-1$, then $ax$ also does but unless $a=1$ these will be in some different order than $0,1,2,dotsc,m-1$.
– Daniel Buck
Aug 2 at 0:16
If $a=2$ and $m=5$, say then $ax$ takes the values $2cdot0,2cdot1,2cdot2,2cdot3,2cdot4$ which we take modulo $5$ to give $0,2,4,1,3$.
– Daniel Buck
Aug 2 at 0:23
Here is another way to show the uniqueness: suppose $x_1$ and $x_2$ are two solutions to (1), we have $a(x_1 - x_2) equiv 0 mod m$. Since $gcd(a,m)=1$, $a^-1$ exists so multiplying $a^-1$ on both sides we get $x_1 equiv x_2 mod m$.
– qweruiop
Aug 2 at 0:39
Yes, that works. Now see if you can extend on that if $gcd(a,m)>1$.
– Daniel Buck
Aug 2 at 0:45
add a comment |Â
(1) has a unique solution is the piece I've been missing. "Then when $x$ runs through a complete residue system modulo $m$, so does $ax$." -- Is this stated as a proposition somewhere?
– qweruiop
Aug 2 at 0:08
Yes, $a$ is a constant, so when $x$ runs through a complete residue system modulo $m$, it takes each of the $m$ values, $0,1,2,dotsc,m-1$, then $ax$ also does but unless $a=1$ these will be in some different order than $0,1,2,dotsc,m-1$.
– Daniel Buck
Aug 2 at 0:16
If $a=2$ and $m=5$, say then $ax$ takes the values $2cdot0,2cdot1,2cdot2,2cdot3,2cdot4$ which we take modulo $5$ to give $0,2,4,1,3$.
– Daniel Buck
Aug 2 at 0:23
Here is another way to show the uniqueness: suppose $x_1$ and $x_2$ are two solutions to (1), we have $a(x_1 - x_2) equiv 0 mod m$. Since $gcd(a,m)=1$, $a^-1$ exists so multiplying $a^-1$ on both sides we get $x_1 equiv x_2 mod m$.
– qweruiop
Aug 2 at 0:39
Yes, that works. Now see if you can extend on that if $gcd(a,m)>1$.
– Daniel Buck
Aug 2 at 0:45
(1) has a unique solution is the piece I've been missing. "Then when $x$ runs through a complete residue system modulo $m$, so does $ax$." -- Is this stated as a proposition somewhere?
– qweruiop
Aug 2 at 0:08
(1) has a unique solution is the piece I've been missing. "Then when $x$ runs through a complete residue system modulo $m$, so does $ax$." -- Is this stated as a proposition somewhere?
– qweruiop
Aug 2 at 0:08
Yes, $a$ is a constant, so when $x$ runs through a complete residue system modulo $m$, it takes each of the $m$ values, $0,1,2,dotsc,m-1$, then $ax$ also does but unless $a=1$ these will be in some different order than $0,1,2,dotsc,m-1$.
– Daniel Buck
Aug 2 at 0:16
Yes, $a$ is a constant, so when $x$ runs through a complete residue system modulo $m$, it takes each of the $m$ values, $0,1,2,dotsc,m-1$, then $ax$ also does but unless $a=1$ these will be in some different order than $0,1,2,dotsc,m-1$.
– Daniel Buck
Aug 2 at 0:16
If $a=2$ and $m=5$, say then $ax$ takes the values $2cdot0,2cdot1,2cdot2,2cdot3,2cdot4$ which we take modulo $5$ to give $0,2,4,1,3$.
– Daniel Buck
Aug 2 at 0:23
If $a=2$ and $m=5$, say then $ax$ takes the values $2cdot0,2cdot1,2cdot2,2cdot3,2cdot4$ which we take modulo $5$ to give $0,2,4,1,3$.
– Daniel Buck
Aug 2 at 0:23
Here is another way to show the uniqueness: suppose $x_1$ and $x_2$ are two solutions to (1), we have $a(x_1 - x_2) equiv 0 mod m$. Since $gcd(a,m)=1$, $a^-1$ exists so multiplying $a^-1$ on both sides we get $x_1 equiv x_2 mod m$.
– qweruiop
Aug 2 at 0:39
Here is another way to show the uniqueness: suppose $x_1$ and $x_2$ are two solutions to (1), we have $a(x_1 - x_2) equiv 0 mod m$. Since $gcd(a,m)=1$, $a^-1$ exists so multiplying $a^-1$ on both sides we get $x_1 equiv x_2 mod m$.
– qweruiop
Aug 2 at 0:39
Yes, that works. Now see if you can extend on that if $gcd(a,m)>1$.
– Daniel Buck
Aug 2 at 0:45
Yes, that works. Now see if you can extend on that if $gcd(a,m)>1$.
– Daniel Buck
Aug 2 at 0:45
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%2f2869495%2fnumber-of-solutions-to-a-linear-congruence-equation%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
If $x_0+z$, where $znedfrack cdot mgcd(a,m)$ then $az=0$ so.....?
– Piquito
Aug 1 at 21:01
So $z propto fracmdiv(a)$ and since $zin mathbbZ$, it must be $z propto fracmcd(a, m)$. Since $cd(a,m) mid gcd(a,m)$, $z propto fracmgcd(a, m)$... Is that the reasoning
– qweruiop
Aug 1 at 23:51