I did find that it can be done arbitrarily. Mind is definitely not into writing about it, though, but here’s the gp code I wrote to look it over.
<pre style="background-color:#ffffff;">
<span style="color:#323232;">/*
</span><span style="color:#323232;"> There may exist a 0<=t<s such that
</span><span style="color:#323232;"> s divides both x and (x+(x%d)*(t*d-1))/d.
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="color:#323232;"> To show this for solving for divisibility of 7 in
</span><span style="color:#323232;"> any natural number x.
</span><span style="color:#323232;">
</span><span style="color:#323232;"> g(35,5,10) = 28
</span><span style="color:#323232;"> g(28,5,10) = 42
</span><span style="color:#323232;"> g(42,5,10) = 14
</span><span style="color:#323232;"> g(14,5,10) = 21
</span><span style="color:#323232;"> g(21,5,10) = 7
</span><span style="color:#323232;">*/
</span><span style="color:#323232;">
</span><span style="color:#323232;">g(x,t,d)=(x+(x%d)*(t*d-1))/d;
</span><span style="color:#323232;">
</span><span style="color:#323232;">/* Find_t( x = Any natural number that is divisible by s,
</span><span style="color:#323232;"> s = The divisor the search is being done for,
</span><span style="color:#323232;"> d = The modulus restriction ).
</span><span style="color:#323232;">
</span><span style="color:#323232;"> Returns all possible t values.
</span><span style="color:#323232;">*/
</span><span style="color:#323232;">
</span><span style="color:#323232;">Find_t(x,s, d) = {
</span><span style="color:#323232;"> V=List();
</span><span style="color:#323232;">
</span><span style="color:#323232;"> for(t=2,d-1,
</span><span style="color:#323232;"> C = factor(g(x,t,d));
</span><span style="color:#323232;"> for(i=1,matsize(C)[1],if(C[i,1]==s, listput(V,t))));
</span><span style="color:#323232;">
</span><span style="color:#323232;"> return(V);
</span><span style="color:#323232;">}
</span>
One thing that I noticed almost right away, regardless what d is, it seems to always work when s is prime, but not when s is composite.
Too tired…Pains too much…Have to stop…But still…interesting.