We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.


Let n be a positive integer. How many different values can gcd(n+5, n+11) attain?

 Aug 27, 2018

First this problem is equivalent  to "Let m be a positive integer such that m>=6,How many different values can gcd(m,m+6) attain?"

Let's proof gcd(m,m+6)<7

Suppose p is factor of m and satisfy p>=7 and m/p=q,that m=p*q.

Then,we can write m+6 as p*q+6

(m+6)%p=(p*q+6)%p=6,that is p can not be factor of m+6

Therefore,gcd(m,m+6)<=6,acctually are the divisors of 6.

Why 4 and 5 can't be attain from gcd(m,m+6)? You can proof it by using above procedure.

1 can be gcd(m,m+6),for example 7 and 13

2 can be gcd(m,m+6),for exampe 8 and 14

3 can be gcd(m,m+6),for exampe 9 and 15

6 can be gcd(m,m+6),for exampe 6 and 12


(I am not a master on number theory.This is just a little thought on this one.By the way,is there any abstract algebra to do this?) 

 Aug 28, 2018

8 Online Users