We call the sequence d1,....,dn of natural numbers, not necessarily distinct, covering if there exists arithmetic progressions like c1+kd1,....,cn+kdn such that every natural number has come in at least one of them. We call this sequence short if we can not delete any of the d1,....,dn such that the resulting sequence be still covering. a) Suppose that d1,....,dn is a short covering sequence and suppose that we've covered all the natural numbers with arithmetic progressions a1+kd1,.....,an+kdn, and suppose that p is a prime number that p divides d1,....,dk but it does not divide dk+1,....,dn. Prove that the remainders of a1,....,ak modulo p contains all the numbers 0,1,.....,p−1. b) Write anything you can about covering sequences and short covering sequences in the case that each of d1,....,dn has only one prime divisor. proposed by Ali Khezeli
Problem
Source: Iran 3rd round 2011-final exam-p8
Tags: algebra proposed, algebra
14.09.2011 00:09
http://www.math.uga.edu/~rlivings/pubs/dcsSurvey.pdf See page 6 , Simpson theorem .
18.09.2011 19:28
Sorry everyone if I'm wrong. If exit t such that p none divided ai−t for i=1,2,...,k then all numbers congruences tmodp must belong aj+k.dj, j>k, .So all numbers divided by p belongs aj−t+kdj , equivalent to exist p.bj+k.p.dj such that all numbers divided by p belong to. Because p none divided dj. Then all numbers belongs in bj+k.dj. That's contradiction. Nk?p
19.09.2011 06:03
hungnguyenvn wrote: .So all numbers divided by p belongs aj−t+kdj , equivalent to exist p.bj+k.p.dj such that all numbers divided by p belong to. Because p none divided dj. Then all numbers belongs in bj+k.dj. That's contradiction. Nk?p I really don't understand what did you do... can you explain me? what means that?
19.09.2011 08:26
Ok,1p,2p,...,np,... belong in aj−t+k.dj . Exist kj min : p|aj−t+kj.dj . p.cj=aj−t+kj.dj, So 1p,2p,...,np,... belong in p.cj+k.dj, chose , kmust=p.k′ because p none divided dj, So then, 1,2,..,n,.. belong in cj+k′.dj. Contradiction,because the"short"
07.11.2019 04:26
Suppose that none of a1,a2,⋯,ak is congruent to i (mod p), for some i. Then, we must have that the arithmetic progressions {ak+1+tdk+1},⋯,{an+tdn} cover all positive integers congruent to i (mod p). We claim that they actually cover all positive integers. If not, suppose that ℓ is not covered. However, by CRT, because p is relatively prime to dk+1dk+2⋯dn, we can take some positive integer α≡i (mod p) and α≡ℓ (mod dk+1dk+2⋯dn). This α isn't covered, but is i (mod p), contradiction. ◻