1
$\begingroup$

Suppose $p$ and $q$ are distinct odd primes. Prove that $\gcd(p+q, p-q) = 2$.

I had figured out that $d$ divides $2p$ and $d$ divides $2q$, but I did not recognize to use coprimeness and divisibility (CAD) to get that $d = 2$.

$\endgroup$
2
  • $\begingroup$ What are your thoughts on the problem so far? $\endgroup$ Dec 3, 2013 at 17:19
  • $\begingroup$ I had figured out that d divides 2p and d divides 2q, but I did not recognize to use coprimeness and divisibility (CAD) to get that d = 2. $\endgroup$
    – rmzep
    Dec 3, 2013 at 17:31

3 Answers 3

8
$\begingroup$

Let $d=\text{gcd}(p+q,p-q)$. Then $d$ divides both $p+q$ and $p-q$, so it divides their sum, which is $2p$. But it also divides their difference, which is $2q$. As $\text{gcd}(p,q)=1$, we must have $d=2$.

$\endgroup$
2
  • $\begingroup$ Doesn't this just show that d divides 2 (not necessarily that d = 2)? $\endgroup$
    – user113324
    Dec 4, 2013 at 5:37
  • $\begingroup$ Technically, yes. So $d=1$ or $2$. But $p$ and $q$ are given as odd primes, so $2$ divides both their sum and their difference. $\endgroup$
    – Doc
    Dec 4, 2013 at 13:54
2
$\begingroup$

Hint $\, $ The linear map $\rm\ (x,y)\mapsto (x+y,x-y)\ $ has determinant $ = \color{#c00}2.\ $ Therefore, from the proof below, we deduce that $\rm\ \gcd(x+y,x-y)\mid \color{#c00}2\, \gcd(x,y)\,\ (\,= \color{#c00}2\ \ if\ \ \gcd(x,y) = 1).$

Inverting a general linear map by Cramer's Rule (multiplying by the adjugate) yields

$$\rm\begin{pmatrix} a & \rm b \\\\ \rm c & \rm d \end{pmatrix}\ \begin{pmatrix} x \\\\ \rm y \end{pmatrix}\ =\ \begin{pmatrix} X \\\\ \rm Y\end{pmatrix}\ \ \ \Rightarrow\ \ \ \begin{array} \rm\Delta\ x\ \ \ =\ \ \ \rm d\ X - b\ Y \\\\ \rm\Delta\ y\ =\ \rm -c\ X + a\ Y \end{array}\ ,\quad\ \Delta\ =\ ad-bc $$

Therefore $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\:x,\:\Delta\:y\ \Rightarrow\ n\ |\ gcd(\Delta\:x,\Delta\:y)\ =\ \Delta\ gcd(x,y)\:.$

So, in particular, if $\rm\:gcd(x,y) = 1\:$ and $\rm\:\Delta\:$ is prime, we conclude that $\rm\:gcd(X,Y) = 1\:$ or $\rm\:\Delta\:.$

Your problem is simply the special case $\rm\ a = c = d = 1,\ b = -1\ \Rightarrow\ \Delta = ad-bc = 2\:.$

This has a very nice arithmetical interpretation in terms of Gaussian integer arithmetic, where the linear map is simply multiplication by $\rm\, 1 + {\it i}.\ $ See this answer for details.

$\endgroup$
1
  • $\begingroup$ An interesting approach. +1. $\endgroup$
    – Potato
    Jan 8, 2014 at 23:16
1
$\begingroup$

$$(p+q,p-q)=d\Longrightarrow d\mid p+q\;\;\text{and}\;\;d\mid p-q$$Adding we have $$d\mid p+q+p-q\Longrightarrow d\mid 2p$$As $(d,p)=1$ then $d=2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.