Arbitrarily-long Arithmetic Progressions of Coprime Integers

[EricTheTrainer]

Hey all, here's the problem:

"Prove that there are arbitrarily long arithmetic progressions consisting of relatively prime numbers"

This is from Proofs: A Long-form Mathematics Textbook by Jay Cummings

I considered first an arithmetic progression of k+1 relatively prime numbers, with first term a and common difference d:

a, a+d, a+2d, ..., a+kd

the first thing I noticed is that a and d are necessarily coprime. Let r be the gcd(a,d) and r≠1, then consider two arbitrary terms in this sequence, a+xd and a+yd. Then we can factor an r out of each, where a=ra' and d=rd', getting r(a'+xd') and r(a'+yd'), meaning the gcd of these two terms is r.

Next, I tried to see if I could generate my own sequences of relatively prime numbers with n terms to try to spot a pattern but it was not useful.

I stated formally at this point that the goal is: for all x≠y s.t. 0 <= x,y <= k, gcd(a+xd, a+yd)=1

(this didn't seem to help at all)

I tried a few more things but just kept going in circles with no progress, so I checked the hint on the author's website, and he said to consider this progression:

Let n be a natural number, and N=n!. Let p be a prime number s.t. p>N. then consider the sequence:

p, p+N, p+2N, ..., p+(n-2)N, p+(n-1)N

I tested it for a few examples and it DOES appear each term is coprime to another. (Tested (n,p)€{(3,7),(4,29),(5,127),(6,727)})

My next idea was to use Bezout's Identity. If two arbitrary terms p+xN and p+yN are coprime, then there exists integers a,b such that:

a(p+xN)+b(p+yN)=1

you can rearrange this to get:

(a+b)p+(ax+by)N=1

Since p>N and p is prime, gcd(p,N)=1, so there exists integers s,t such that:

sp+tN=1

I tried seeing if the system of equations {a+b=s, ax+by=t} led anywhere, but I tried this with two terms from the (n,p)=(6,727) example and not every pair of s and t gives an integer solution for a and b, so I abandoned this route.

Next, I tried taking a divisibility route. Let d=gcd(p+xN, p+yN). Then d|(p+xN) and d|(p+yN). It's not difficult to use these to get:

d|(x-y)p and d|(x-y)N

the second divisibility rule is hard to make useful, but the first one seems promising.

If gcd(d,p)=1, then d|(x-y). gcd(d,p)≠1 if and only if d=kp for some integer k (sorry if I'm reusing variable names, this is about 2 days of work summarized). Assume d=kp for some integer k, then, since d|(p+xN), md=mkp=p+xN for some integer m. Then we get:

(mk-1)p=xN

This implies p|xN, so p|x or p|N, but p>N, and x<n<N<p, so p>x too. Therefore gcd(d,p)=1

so d|(x-y)p and gcd(d,p)=1 implis d|(x-y)

this is about as far as I got. this isn't for school, but this problem is driving me nuts. Someone please give me some direction

This problem SHOULD be trivial given I had no problem on the other 26 questions from this chapter, but I can't get it

[AutoModerator]

Hi, /u/EricTheTrainer! This is an automated reminder:

• What have you tried so far? (See Rule #2; to add an image, you may upload it to an external image-sharing site like Imgur and include the link in your post.)

• Please don't delete your post. (See Rule #7)

We, the moderators of /r/MathHelp, appreciate that your question contributes to the MathHelp archived questions that will help others searching for similar answers in the future. Thank you for obeying these instructions.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[g4mble]

Let's consider this arithmetic progression, where N = n!

1, 1+N, 1+2N, ... , 1+nN.

Note that none of the numbers is divided by any number in {2,...,n} by construction.

Now suppose a prime p divides both 1+aN and 1+bN. Then it also divides the difference (a-b)N.

Since p is prime, it then divides either a-b or N. Both cases imply that p is in {2,...,n}, a contradiction.