We call the sequence $d_1,....,d_n$ of natural numbers, not necessarily distinct, covering if there exists arithmetic progressions like $c_1+kd_1$,....,$c_n+kd_n$ 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 $d_1,....,d_n$ such that the resulting sequence be still covering. a) Suppose that $d_1,....,d_n$ is a short covering sequence and suppose that we've covered all the natural numbers with arithmetic progressions $a_1+kd_1,.....,a_n+kd_n$, and suppose that $p$ is a prime number that $p$ divides $d_1,....,d_k$ but it does not divide $d_{k+1},....,d_n$. Prove that the remainders of $a_1,....,a_k$ 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 $d_1,....,d_n$ 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 $a_i -t$ for $i =1,2,...,k$ then all numbers congruences $ t mo d p$ must belong $a_j +k.d_j$, $j>k$, .So all numbers divided by $p$ belongs $a_j - t+kd_j$ , equivalent to exist $p.b_j + k.p.d_j$ such that all numbers divided by $p$ belong to. Because $p$ none divided $d_j$. Then all numbers belongs in $b_j +k.d_j$. That's contradiction. Nk?p
19.09.2011 06:03
hungnguyenvn wrote: .So all numbers divided by $p$ belongs $a_j - t+kd_j$ , equivalent to exist $p.b_j + k.p.d_j$ such that all numbers divided by $p$ belong to. Because $p$ none divided $d_j$. Then all numbers belongs in $b_j +k.d_j$. 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 ${a_j -t +k.d_j}$ . Exist $k_j$ min : $p | a_j-t+k_j.d_j$ . $p.c_j=a_j-t+k_j.d_j$, So $1p,2p,...,np,...$ belong in $p.c_j +k.d_j$, chose , $k must =p.k'$ because $p$ none divided $d_j$, So then, $1,2,..,n,..$ belong in $c_j+ k'.d_j$. Contradiction,because the"short"
07.11.2019 04:26
Suppose that none of $a_1, a_2, \cdots, a_k$ is congruent to $i$ (mod $p$), for some $i.$ Then, we must have that the arithmetic progressions $\{a_{k+1} + td_{k+1}\}, \cdots, \{a_n + t d_n\}$ cover all positive integers congruent to $i$ (mod $p$). We claim that they actually cover all positive integers. If not, suppose that $\ell$ is not covered. However, by CRT, because $p$ is relatively prime to $d_{k+1} d_{k+2} \cdots d_n$, we can take some positive integer $\alpha \equiv i$ (mod $p$) and $\alpha \equiv \ell$ (mod $d_{k+1} d_{k+2} \cdots d_n$). This $\alpha$ isn't covered, but is $i$ (mod $p$), contradiction. $\square$