SOLVED Two consecutive numbers are relatively prime

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
Two consecutive numbers are relatively prime.

\(\displaystyle (n, n+1)=1\rightarrow \alpha n+\beta (n+1)=1\)

I am not sure what to do next to prove this.
 

[email protected]

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
Two consecutive numbers are relatively prime.

\(\displaystyle (n, n+1)=1\rightarrow \alpha n+\beta (n+1)=1\)

I am not sure what to do next to prove this.
\(\displaystyle \alpha=-1,\; \beta=1 \)
 

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
I see how that will justify the equality but is that ok to do for the proof and then just call it day and it is done?
 

[email protected]

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
I see how that will justify the equality but is that ok to do for the proof and then just call it day and it is done?
Let \(\displaystyle g=(n,n+1) \)

\(\displaystyle g\mid n \) and \(\displaystyle g\mid n+1 \implies g\mid (n+1)-n = 1 \implies g=\pm1 \). But since \(\displaystyle g>0 \), we get \(\displaystyle g=1 \).
 
Jun 2010
148
110
Israel
I see how that will justify the equality but is that ok to do for the proof and then just call it day and it is done?
The answer is yes. In general: Let \(\displaystyle a\) and \(\displaystyle b\) be integers. There exists two integers \(\displaystyle x\) and \(\displaystyle y\) such that \(\displaystyle ax+by=1\) if and only if \(\displaystyle (a,b)=1\). In your case, \(\displaystyle a=n\), \(\displaystyle x=-1\) and \(\displaystyle b=n
+1\), \(\displaystyle y=1\).

However, the reply you got from "chiph588" using the greatest common divisor (\(\displaystyle g=(n,n+1)\)) seems to me more elegant.
 

[email protected]

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
The answer is yes. In general: Let \(\displaystyle a\) and \(\displaystyle b\) be integers. There exists two integers \(\displaystyle x\) and \(\displaystyle y\) such that \(\displaystyle ax+by=1\) if and only if \(\displaystyle (a,b)=1\). In your case, \(\displaystyle a=n\), \(\displaystyle x=-1\) and \(\displaystyle b=n
+1\), \(\displaystyle y=1\).
This is a special case of Bézout's identity.