+0  
 
0
1254
1
avatar

 

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

 Aug 27, 2018
 #1
avatar
+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?) 

 Aug 28, 2018

1 Online Users

avatar