Dtjytyk

Sum letters are not two different

How to write capital alpha?

Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?

Do I really need to have a message in a novel to appeal to readers?

Google .dev domain strangely redirects to https

Random body shuffle every night—can we still function?

How does light 'choose' between wave and particle behaviour?

preposition before coffee

Is it possible for SQL statements to execute concurrently within a single session in SQL Server?

Lagrange four-squares theorem --- deterministic complexity

Why are my pictures showing a dark band on one edge?

As Singapore Airlines (Krisflyer) Gold, can I bring my family into the lounge on a domestic Virgin Australia flight?

What is the meaning of 'breadth' in breadth first search?

Is there any word for a place full of confusion?

How does Belgium enforce obligatory attendance in elections?

An adverb for when you're not exaggerating

How to run automated tests after each commit?

Is multiple magic items in one inherently imbalanced?

How could we fake a moon landing now?

What to do with repeated rejections for phd position

Is there public access to the Meteor Crater in Arizona?

What are the discoveries that have been possible with the rejection of positivism?

Dyck paths with extra diagonals from valleys (Laser construction)

Can the Flaming Sphere spell be rammed into multiple Tiny creatures that are in the same 5-foot square?

Show that the equation $axequiv 1 pmod{n}$ has a solution for some integer $x$ if and only if $gcd(a,n) = 1$.

1

$begingroup$

Let $a$ and $n$ be positive integers, and let $d = gcd(a, n)$. Show that the
equation $axequiv 1 pmod{n}$ has a solution for some integer $x$ if and only if
$d = 1$".

I know that if $axequiv 1 pmod{n}$, then $ax=nu+1$ giving $1=ax-nu$, meaning $d=1$. However, I'm not sure what to do for proving the other direction. Any help is appreciated.

elementary-number-theory proof-writing modular-arithmetic

share|cite|improve this question

edited Sep 17 '18 at 7:38

thesmallprint

2,7201618

asked Sep 17 '18 at 6:56

Henry MullenHenry Mullen

262

$endgroup$

add a comment | 

1

$begingroup$

Let $a$ and $n$ be positive integers, and let $d = gcd(a, n)$. Show that the
equation $axequiv 1 pmod{n}$ has a solution for some integer $x$ if and only if
$d = 1$".

I know that if $axequiv 1 pmod{n}$, then $ax=nu+1$ giving $1=ax-nu$, meaning $d=1$. However, I'm not sure what to do for proving the other direction. Any help is appreciated.

elementary-number-theory proof-writing modular-arithmetic

share|cite|improve this question

edited Sep 17 '18 at 7:38

thesmallprint

2,7201618

asked Sep 17 '18 at 6:56

Henry MullenHenry Mullen

262

$endgroup$

add a comment | 

$begingroup$

Let $a$ and $n$ be positive integers, and let $d = gcd(a, n)$. Show that the
equation $axequiv 1 pmod{n}$ has a solution for some integer $x$ if and only if
$d = 1$".

I know that if $axequiv 1 pmod{n}$, then $ax=nu+1$ giving $1=ax-nu$, meaning $d=1$. However, I'm not sure what to do for proving the other direction. Any help is appreciated.

elementary-number-theory proof-writing modular-arithmetic

share|cite|improve this question

edited Sep 17 '18 at 7:38

thesmallprint

2,7201618

asked Sep 17 '18 at 6:56

Henry MullenHenry Mullen

262

$endgroup$

share|cite|improve this question

edited Sep 17 '18 at 7:38

thesmallprint

2,7201618

asked Sep 17 '18 at 6:56

Henry MullenHenry Mullen

262

share|cite|improve this question

edited Sep 17 '18 at 7:38

thesmallprint

2,7201618

asked Sep 17 '18 at 6:56

Henry MullenHenry Mullen

262

edited Sep 17 '18 at 7:38

thesmallprint

2,7201618

edited Sep 17 '18 at 7:38

thesmallprint

2,7201618

asked Sep 17 '18 at 6:56

Henry MullenHenry Mullen

262

asked Sep 17 '18 at 6:56

Henry MullenHenry Mullen

262

4 Answers
4

active

oldest

votes

2

$begingroup$

From Bezout's identity, we have $ax+bn=1$ if and only if $gcd(a,n)=1$. $ax+bn=1$ same as, $axequiv 1pmod{n}$.

share|cite|improve this answer

answered Sep 17 '18 at 7:55

OppoInfinityOppoInfinity

18911

$endgroup$

add a comment | 

1

$begingroup$

You have solved the 'only if' part. This can be a way to proceed for the 'if' part. Now, we have $d=1$ which means that $gcd(a,n)=1$. Consider the set $[ai] bmod n $ for $i$ ranging from $1$ to $n$. If we have:
$$ai=aj pmod n$$
Then $n$ divides $a(i-j)$. As $gcd(a,n)=1$, $n$ divides $i-j$ and since $i,j$ range from $1$ to $n$, $i=j$. This means that two distinct elements of our set are always different. Since there are $n$ values in the set, and there are $n$ possible remainders, one of them must be $1$ which proves the existence of $i$ for which $ai=1 pmod n$.

share|cite|improve this answer

answered Sep 17 '18 at 7:09

HaranHaran

1,159424

$endgroup$

add a comment | 

0

$begingroup$

(i) If $axequiv 1 pmod{n}$ has a solution, then you can write $ax - bn = 1, binmathbb{Z}$. No prime number divides $1$, so $gcd(a,n) = 1$.

(RRA argument shows you that by assuming there is a prime $p|d=gcd(a,n)$, you can factor $p(a'x - bn') = 1Rightarrow p|1$, absurd.)

(ii) If $gcd(a,n) = 1$, then we have $axequiv ypmod{n}$ for arbitrary units $xnotequiv y$ and $y$ must assume the value $1$ for some value of $x$ since ${au_1,ldots , au_{phi(n)}}$ is a reduced residue system modulo $n$ (the set of units mod $n$).

(By RRA, suppose you test all $phi(n)$ units for $x$ but none yields $axequiv 1pmod{n}$. Thus $y$ assumes less than $phi(n)$ values. So we have a repetition such that $avequiv uequiv av'pmod{n}Rightarrow vequiv v'pmod{n}$ for two different units $v, v'$, contradicting $xnotequiv y$.)

share|cite|improve this answer

answered Mar 25 at 16:44

Rick AlmeidaRick Almeida

1989

$endgroup$

add a comment | 

-1

$begingroup$

By Euler's Theorem , $a^{phi(n)} = 1 (mathrm{mod}~n)$ if $n$ and $a$ are co-prime.
Thus, you can directly take $x = a^{phi(n) - 1}$ to satisfy the equation.

share|cite|improve this answer

answered Sep 17 '18 at 7:02

Colin SmithColin Smith

142

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Can you prove Euler's theorem without using the fact that if $gcd(a,n)=1$ then $a$ is invertible modulo $n$?
  $endgroup$
  – Lord Shark the Unknown
  Sep 17 '18 at 7:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  One way to prove it is by using Extended Euclidean algorithm. The algorithm itself no only gives a way to calculate x, but also proves such x always exists. There are also other proofs not using this fact on Wikipedia.
  $endgroup$
  – Colin Smith
  Sep 17 '18 at 7:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I have given a proof using the fact that $a$ is invertible modulo $n$
  $endgroup$
  – Haran
  Sep 17 '18 at 7:16
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2919902%2fshow-that-the-equation-ax-equiv-1-pmodn-has-a-solution-for-some-integer-x%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

From Bezout's identity, we have $ax+bn=1$ if and only if $gcd(a,n)=1$. $ax+bn=1$ same as, $axequiv 1pmod{n}$.

share|cite|improve this answer

answered Sep 17 '18 at 7:55

OppoInfinityOppoInfinity

18911

$endgroup$

add a comment | 

2

$begingroup$

From Bezout's identity, we have $ax+bn=1$ if and only if $gcd(a,n)=1$. $ax+bn=1$ same as, $axequiv 1pmod{n}$.

share|cite|improve this answer

answered Sep 17 '18 at 7:55

OppoInfinityOppoInfinity

18911

$endgroup$

add a comment | 

$begingroup$

From Bezout's identity, we have $ax+bn=1$ if and only if $gcd(a,n)=1$. $ax+bn=1$ same as, $axequiv 1pmod{n}$.

share|cite|improve this answer

answered Sep 17 '18 at 7:55

OppoInfinityOppoInfinity

18911

$endgroup$

share|cite|improve this answer

answered Sep 17 '18 at 7:55

OppoInfinityOppoInfinity

18911

answered Sep 17 '18 at 7:55

OppoInfinityOppoInfinity

18911

answered Sep 17 '18 at 7:55

OppoInfinityOppoInfinity

18911

1

$begingroup$

You have solved the 'only if' part. This can be a way to proceed for the 'if' part. Now, we have $d=1$ which means that $gcd(a,n)=1$. Consider the set $[ai] bmod n $ for $i$ ranging from $1$ to $n$. If we have:
$$ai=aj pmod n$$
Then $n$ divides $a(i-j)$. As $gcd(a,n)=1$, $n$ divides $i-j$ and since $i,j$ range from $1$ to $n$, $i=j$. This means that two distinct elements of our set are always different. Since there are $n$ values in the set, and there are $n$ possible remainders, one of them must be $1$ which proves the existence of $i$ for which $ai=1 pmod n$.

share|cite|improve this answer

answered Sep 17 '18 at 7:09

HaranHaran

1,159424

$endgroup$

add a comment | 

1

$begingroup$

You have solved the 'only if' part. This can be a way to proceed for the 'if' part. Now, we have $d=1$ which means that $gcd(a,n)=1$. Consider the set $[ai] bmod n $ for $i$ ranging from $1$ to $n$. If we have:
$$ai=aj pmod n$$
Then $n$ divides $a(i-j)$. As $gcd(a,n)=1$, $n$ divides $i-j$ and since $i,j$ range from $1$ to $n$, $i=j$. This means that two distinct elements of our set are always different. Since there are $n$ values in the set, and there are $n$ possible remainders, one of them must be $1$ which proves the existence of $i$ for which $ai=1 pmod n$.

share|cite|improve this answer

answered Sep 17 '18 at 7:09

HaranHaran

1,159424

$endgroup$

add a comment | 

$begingroup$

You have solved the 'only if' part. This can be a way to proceed for the 'if' part. Now, we have $d=1$ which means that $gcd(a,n)=1$. Consider the set $[ai] bmod n $ for $i$ ranging from $1$ to $n$. If we have:
$$ai=aj pmod n$$
Then $n$ divides $a(i-j)$. As $gcd(a,n)=1$, $n$ divides $i-j$ and since $i,j$ range from $1$ to $n$, $i=j$. This means that two distinct elements of our set are always different. Since there are $n$ values in the set, and there are $n$ possible remainders, one of them must be $1$ which proves the existence of $i$ for which $ai=1 pmod n$.

share|cite|improve this answer

answered Sep 17 '18 at 7:09

HaranHaran

1,159424

$endgroup$

share|cite|improve this answer

answered Sep 17 '18 at 7:09

HaranHaran

1,159424

answered Sep 17 '18 at 7:09

HaranHaran

1,159424

answered Sep 17 '18 at 7:09

HaranHaran

1,159424

0

$begingroup$

(i) If $axequiv 1 pmod{n}$ has a solution, then you can write $ax - bn = 1, binmathbb{Z}$. No prime number divides $1$, so $gcd(a,n) = 1$.

(RRA argument shows you that by assuming there is a prime $p|d=gcd(a,n)$, you can factor $p(a'x - bn') = 1Rightarrow p|1$, absurd.)

(ii) If $gcd(a,n) = 1$, then we have $axequiv ypmod{n}$ for arbitrary units $xnotequiv y$ and $y$ must assume the value $1$ for some value of $x$ since ${au_1,ldots , au_{phi(n)}}$ is a reduced residue system modulo $n$ (the set of units mod $n$).

(By RRA, suppose you test all $phi(n)$ units for $x$ but none yields $axequiv 1pmod{n}$. Thus $y$ assumes less than $phi(n)$ values. So we have a repetition such that $avequiv uequiv av'pmod{n}Rightarrow vequiv v'pmod{n}$ for two different units $v, v'$, contradicting $xnotequiv y$.)

share|cite|improve this answer

answered Mar 25 at 16:44

Rick AlmeidaRick Almeida

1989

$endgroup$

add a comment | 

0

$begingroup$

(i) If $axequiv 1 pmod{n}$ has a solution, then you can write $ax - bn = 1, binmathbb{Z}$. No prime number divides $1$, so $gcd(a,n) = 1$.

(RRA argument shows you that by assuming there is a prime $p|d=gcd(a,n)$, you can factor $p(a'x - bn') = 1Rightarrow p|1$, absurd.)

(ii) If $gcd(a,n) = 1$, then we have $axequiv ypmod{n}$ for arbitrary units $xnotequiv y$ and $y$ must assume the value $1$ for some value of $x$ since ${au_1,ldots , au_{phi(n)}}$ is a reduced residue system modulo $n$ (the set of units mod $n$).

(By RRA, suppose you test all $phi(n)$ units for $x$ but none yields $axequiv 1pmod{n}$. Thus $y$ assumes less than $phi(n)$ values. So we have a repetition such that $avequiv uequiv av'pmod{n}Rightarrow vequiv v'pmod{n}$ for two different units $v, v'$, contradicting $xnotequiv y$.)

share|cite|improve this answer

answered Mar 25 at 16:44

Rick AlmeidaRick Almeida

1989

$endgroup$

add a comment | 

$begingroup$

(i) If $axequiv 1 pmod{n}$ has a solution, then you can write $ax - bn = 1, binmathbb{Z}$. No prime number divides $1$, so $gcd(a,n) = 1$.

(RRA argument shows you that by assuming there is a prime $p|d=gcd(a,n)$, you can factor $p(a'x - bn') = 1Rightarrow p|1$, absurd.)

(ii) If $gcd(a,n) = 1$, then we have $axequiv ypmod{n}$ for arbitrary units $xnotequiv y$ and $y$ must assume the value $1$ for some value of $x$ since ${au_1,ldots , au_{phi(n)}}$ is a reduced residue system modulo $n$ (the set of units mod $n$).

(By RRA, suppose you test all $phi(n)$ units for $x$ but none yields $axequiv 1pmod{n}$. Thus $y$ assumes less than $phi(n)$ values. So we have a repetition such that $avequiv uequiv av'pmod{n}Rightarrow vequiv v'pmod{n}$ for two different units $v, v'$, contradicting $xnotequiv y$.)

share|cite|improve this answer

answered Mar 25 at 16:44

Rick AlmeidaRick Almeida

1989

$endgroup$

share|cite|improve this answer

answered Mar 25 at 16:44

Rick AlmeidaRick Almeida

1989

answered Mar 25 at 16:44

Rick AlmeidaRick Almeida

1989

answered Mar 25 at 16:44

Rick AlmeidaRick Almeida

1989

-1

$begingroup$

By Euler's Theorem , $a^{phi(n)} = 1 (mathrm{mod}~n)$ if $n$ and $a$ are co-prime.
Thus, you can directly take $x = a^{phi(n) - 1}$ to satisfy the equation.

share|cite|improve this answer

answered Sep 17 '18 at 7:02

Colin SmithColin Smith

142

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Can you prove Euler's theorem without using the fact that if $gcd(a,n)=1$ then $a$ is invertible modulo $n$?
  $endgroup$
  – Lord Shark the Unknown
  Sep 17 '18 at 7:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  One way to prove it is by using Extended Euclidean algorithm. The algorithm itself no only gives a way to calculate x, but also proves such x always exists. There are also other proofs not using this fact on Wikipedia.
  $endgroup$
  – Colin Smith
  Sep 17 '18 at 7:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I have given a proof using the fact that $a$ is invertible modulo $n$
  $endgroup$
  – Haran
  Sep 17 '18 at 7:16
  

  
  
  
  

add a comment | 

-1

$begingroup$

By Euler's Theorem , $a^{phi(n)} = 1 (mathrm{mod}~n)$ if $n$ and $a$ are co-prime.
Thus, you can directly take $x = a^{phi(n) - 1}$ to satisfy the equation.

share|cite|improve this answer

answered Sep 17 '18 at 7:02

Colin SmithColin Smith

142

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Can you prove Euler's theorem without using the fact that if $gcd(a,n)=1$ then $a$ is invertible modulo $n$?
  $endgroup$
  – Lord Shark the Unknown
  Sep 17 '18 at 7:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  One way to prove it is by using Extended Euclidean algorithm. The algorithm itself no only gives a way to calculate x, but also proves such x always exists. There are also other proofs not using this fact on Wikipedia.
  $endgroup$
  – Colin Smith
  Sep 17 '18 at 7:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I have given a proof using the fact that $a$ is invertible modulo $n$
  $endgroup$
  – Haran
  Sep 17 '18 at 7:16
  

  
  
  
  

add a comment | 

$begingroup$

By Euler's Theorem , $a^{phi(n)} = 1 (mathrm{mod}~n)$ if $n$ and $a$ are co-prime.
Thus, you can directly take $x = a^{phi(n) - 1}$ to satisfy the equation.

share|cite|improve this answer

answered Sep 17 '18 at 7:02

Colin SmithColin Smith

142

$endgroup$

share|cite|improve this answer

answered Sep 17 '18 at 7:02

Colin SmithColin Smith

142

answered Sep 17 '18 at 7:02

Colin SmithColin Smith

142

answered Sep 17 '18 at 7:02

Colin SmithColin Smith

142