find if any number in A.P can be divided by a given number(k).

Question

If there is any method other than finding each number of A.P iteratively and check if it is divisible by k or not?

Example :

Tn = 11*n+d;

k = 7;

find if (Tn % k == 0) ?

Answer 1

Collating comments...

$T_n = an + d$ will be divisible by $k$ if and only if

$an+d\equiv 0\pmod{k}$ if and only if

$a'n + d'\equiv 0\pmod{k'}$ where $a' = \frac{a}{\gcd(a,d,k)}, d'=\frac{d}{\gcd(a,d,k)}$ and $k'=\frac{k}{\gcd(a,d,k)}$

if and only if $(a')^{-1}$ exists in $(\Bbb Z_{k'},+,\times)$

if and only if $\gcd(a',k')=1$

if and only if $n\equiv (-d')\cdot (a')^{-1}\pmod{k'}$

---

Examples:

Asking what values of $n$ are such that $T_n = 11n+5$ is divisible by $7$, we have that $\gcd(11,7)=1$ that $11^{-1}\equiv 2\pmod{7}$ and $(-5)\cdot 11^{-1}\equiv 4\pmod{7}$ so we find that every $n$ of the form $7m+4$ will be such that $T_n$ is divisible by $7$. (Indeed, $T_4=49=7\cdot 7,~T_{11}=126=7\cdot 18,~T_{18}=203=7\cdot 29,\dots$)

Asking what values of $n$ are such that $T_n = 60n + 6$ is divisible by $30$, we look instead at which $n$ are such that $10n+1$ are divisible by $5$, but since $\gcd(10,1)\neq 1$ while $\gcd(1,5)=1$ we see that there are no solutions.

Finally, asking what values of $n$ are such that $T_n = 8n+4$ is divisible by $12$, we look instead at which $n$ are such that $2n+1$ is divisible by $3$. Since $\gcd(2,3)=1$, $2^{-1}\equiv 2\pmod{3}$ and $(-1)\cdot 2^{-1}\equiv 1\pmod{3}$ we have that every $n$ of the form $3m+1$ works. (Indeed, $T_1=12, T_4=36=12\cdot 3, T_7=60=12\cdot 5,\dots$)