# gcd(n, n+p)

• Dec 11th 2010, 11:56 AM
gcd(n, n+p)
Hello all,
Given a prime number p and an integer n. Prove that gcd(n, n+p) is either 1 or p.
If p is less than n, then we have two cases: either n is a multiple of p, and then we'll get that the gcd is equal to p, or n is not a multiple of p, and then we'll get that the gcd is equal to 1.
However, if n is less than p, then we must get a 1 (we can't get p since p>n). I didn't figure out how to prove that! Need your help!

Thank you

• Dec 11th 2010, 12:25 PM
melese
Actually it's quite simple if you approach the problem differently... No need for examination of cases.

$gcd(n,n+p)$ by definition divides both $n$ and $p$; thus it also divides their difference, $(n+p)-n$.
Hence $gcd(n,n+p)$ divides $p$. But since $p$ is prime $gcd(n,n+p)$ is equal to either $1$ or $p$ (the only divisors of $p$.)
• Dec 11th 2010, 06:34 PM
dwsmith
Let the $gcd(n,n+p)=d$

Since d is a common divisor, $n=md \ \mbox{and} \ n+p=rd$ such that $n,m\in\mathbb{Z}$.

Then by addition we obtain $n+(n+p)=d(m+r)\Rightarrow d|[n+(n+p)]$.

Now, $d|n \ \mbox{and} \ d|(n+p)$

Thus, it is trivial that 1 divides n and n+p.

Now, since $d|(n+p), \ \mbox{then} \ d|n \ \mbox{and} \ d|p$

Since p is prime, d can only be 1 or p.
• Dec 11th 2010, 07:25 PM
tonio
Quote:

Originally Posted by dwsmith
Let the $gcd(n,n+p)=d$ such that d is either 1 or p.

You can't begin a proof by assuming that what you want to prove is true...!

Since d is a common divisor, $n=md \ \mbox{and} \ n+p=rd$ such that $n,m\in\mathbb{Z}$.

Then by addition we obtain $n+(n+p)=d(m+r)$.

Now, $d|n \ \mbox{and} \ d|(n+p)$

Thus, it is trivial that 1 divides n and n+p.

"Thus"? this is trivial and it doesn't follow from the above!

I think Melese's proof is correct, short and pretty concise. Nothing more is needed and

the above (and below) doesn't add, imo, any clearity to this matter.

Tonio

Now, since $d|(n+p), \ \mbox{then} \ d|n \ \mbox{and} \ d|p$

Since p is prime, d can only be 1 or p.

.
• Dec 11th 2010, 07:38 PM
dwsmith
You are correct about saying d is 1 and p but I beg to differ on the rest.

$d(m+r)=dq$ where q=m+r. Now, $dq=[n+(n+p)]\Rightarrow d|[n+(n+p)]\Rightarrow d|n \ \mbox{and} \ d|(n+p)$

Clearly, if d is 1, it is true sinc $1|n\Rightarrow 1*k=n, \ k=n \ \mbox{and} \ 1*t=n+p, \ t=n+p$

Thus, 1 is a trivial case since it always works.

Now, examining $d|(n+p)\Rightarrow d|n \ \mbox{and} \ d|p$ which leads d=1 or p since 1 or the prime number divides p.

Also, it does add value. Not everyone thinks the same way and I don't prefer Melese proof. That doesn't mean I discredit his work. I appreciate it his work since it has benefited me in the past.
• Dec 11th 2010, 07:46 PM
tonio
Quote:

Originally Posted by dwsmith
You are correct about saying d is 1 and p but I beg to differ on the rest.

$d(m+r)=dq$ where q=m+r. Now, $dq=[n+(n+p)]\Rightarrow d|[n+(n+p)]\Rightarrow d|n \ \mbox{and} \ d|(n+p)$

No, by all means no!! It isn't true at all that $d\mid [n+(n+p)]\Longrightarrow d\mid n\,\,and\,\,d\mid (n+p)$ .

For example, take $d=3\,,\,n=1\,,\,p=19.\,\,Then\,\,3\mid 1+(1+19)\,,\,\,but\,\,3\nmid 1\,\,and\,\,3\nmid (1+19)$ !

Clearly, if d is 1, it is true sinc $1|n\Rightarrow 1*k=n, \ k=n \ \mbox{and} \ 1*t=n+p, \ t=n+p$

Thus, 1 is a trivial case since it always works.

Now, examining $d|(n+p)\Rightarrow d|n \ \mbox{and} \ d|p$

Again, this doesn't follow!

I think you must check your logical deductions in this matter very carefully.

Tonio

which leads d=1 or p since 1 or the prime number divides p.

Also, it does add value. Not everyone thinks the same way and I don't prefer Melese proof. That doesn't mean I discredit his work. I appreciate it his work since it has benefited me in the past.

.
• Dec 11th 2010, 07:51 PM
dwsmith
If $n=1$ and $n+p=20$, the $gcd(1,20)\neq 3$
• Dec 11th 2010, 07:54 PM
tonio
Quote:

Originally Posted by dwsmith
If $n=1$ and $n+p=20$, the $gcd(1,20)\neq 3$

Who cares?! You wrote $A\Longrightarrow B$ and, as shown in my past post, this is false. In mathematics such a thing

doesn't force you to go back all the way, [U]unless[U] you specifically write so, and you didn't (and well

done since in this case that wouldn't work either)

Tonio
• Dec 11th 2010, 08:02 PM
dwsmith
If we are given $gcd(a,b)=m$, then $m|a \ \mbox{and} \ m|b$.

Now, if we have the $gcd(n,n+p)=d$, then $gcd\left(\frac{n}{d},\frac{n+p}{d}\right)=1$.

Therefore, $d|n \ \mbox{and} \ d|(n+p)$
• Dec 11th 2010, 08:10 PM
tonio
Quote:

Originally Posted by dwsmith
If we are given $gcd(a,b)=m$, then $m|a \ \mbox{and} \ m|b$.

Now, if we have the $gcd(n,n+p)=d$, then $gcd\left(\frac{n}{d},\frac{n+p}{d}\right)=1$.

Therefore, $d|n \ \mbox{and} \ d|(n+p)$

Now that is true, but it's way different from what you wrote the first time...can you tell?

And again, you make things messier than necessary: what does "Now, if we have the $gcd(n,n+p)=d\,\,then\,\,gcd(n/d,(n+p)/d)=1$"

have to do with this?? Simply, by definition, $gcd(n,n+p)=d\Longrightarrow d\mid n\,,\,d\mid (n+p)$ , period.

Tonio
• Dec 11th 2010, 08:18 PM
dwsmith
Would you accept my OP if I added the definition in?
• Dec 11th 2010, 08:23 PM
tonio
Quote:

Originally Posted by dwsmith
Would you accept my OP if I added the definition in?

No. It is flawed from the beginning and all through, and you didn't actually prove anything.

When I said that Melese's proof is nice is because it's the shortest and clearest I know, not

comparing it with yours since yours is not a proof.

I'm not trying to offend or hurt, I'm just pointing out a fact.

Tonio
• Dec 11th 2010, 08:28 PM
dwsmith
You still haven't convinced me it is wrong though.

Since $d|n$ and $d|(n+p)$, of course 1 is a possible solution.

$gcd(n,p)=y$

$y|n$ and $y|p$ but we also know $d|n$

$y|(n+p)$ but $d|(n+p)$ so $y=d$.

Since $y=d$, $d|p$. $d*h=p$ and p is prime so only 1 and the actually prime number, p, will divide p.
• Dec 12th 2010, 03:49 AM
tonio
Quote:

Originally Posted by dwsmith
Let the $gcd(n,n+p)=d$

Since d is a common divisor, $n=md \ \mbox{and} \ n+p=rd$ such that $n,m\in\mathbb{Z}$.

Then by addition we obtain $n+(n+p)=d(m+r)\Rightarrow d|[n+(n+p)]$.

Now, $d|n \ \mbox{and} \ d|(n+p)$

Thus, it is trivial that 1 divides n and n+p.

Now, since $d|(n+p), \ \mbox{then} \ d|n \ \mbox{and} \ d|p$

Since p is prime, d can only be 1 or p.

Ok then. I really think you honestly believe that what you wrote is correct in some sense, and I'll try to show you that

you're wrong. The above is your first post, and let's try to analyze it carefully, shall we?

To begin with, to establish as assumption what has to be proved is incorrect, as we already agreed, and as I can see

you already erased it and some other stuff. Good.

Next, lines 2 and 3 are completely innecessary except for the very last part of line 3 (and even then it

should better be a rest and not a sum), since what's written in line 4 follows directly from line 1, i.e. from $gcd(n,n+p)=d$ .

Line 5 is wrong from a logical and semantic point of view: that "thus" there renders false the whole line. The number 1 divides

ANYTHING in $\mathbb{Z}$ , whether what you wrote in lines 2,3,4 is false or true. Writing that thus makes

the whole thing even more confusing and false, since it does NOT follow from line 4!

Line 6 is plainly false: it doesn't follow that $d\mid n\,\,and\,\,d\mid p$ from $d\mid(n+p)$ . It follows from $d\mid n\,\,and\,\,\d\mid (n+p)\Longrightarrow d\mid [(n+p)-p=p]$ .

In particular, that "then" before $d\mid n$ is very confusing, since, again, this follows from the

very definition of gcd and from line 1 !, not from the first part of line 6.

Resuming Melese's proof, it is the simplest thing: $(n,n+p)=d\Longrightarrow d\mid n\,,\,d\mid (n+p)\Longrightarrow d\mid [(n+p)-n=p]\Longrightarrow d\mid p\Longleftrightarrow d=1\,\,or\,\,p$

Tonio