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

17 Online Users


New Privacy Policy

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