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.
Please click on "Accept cookies" if you agree to the setting of cookies. Cookies that do not require consent remain unaffected by this, see
cookie policy and privacy policy.
DECLINE COOKIES

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

Guest Aug 27, 2018

#1**+2 **

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?)

Guest Aug 28, 2018