Let us consider the $n$-element strings in the form $q_1 q_2 \dots q_n$, where $q_i$ is an integer in $\{0,1,\dots,d-1\}$ $\forall i$. These strings are in total $d^n$.
How many strings are such that the product of their elements $\prod_{i=1}^n q_i$ is congruent to 0 mod $d$?
I can calculate this number for some specific cases: $d$ prime, $d$ square of prime, $d$ product of primes. For example, for $d$ prime I get $d^n - (d-1)^n$. But I cannot progress much on the general case...
Does anyone know any reference dealing with this problem? Thank you in advance!
Let $d=\prod_ip_i^{k_i}$ be the prime factorization of $d$. The key is to note that the events for different $i$ that the product of a uniformly randomly selected string is divisible by $p_i^{k_i}$ are independent. This is because requiring that a certain element of the string not be divisible by a certain power of $p_j$ leaves the proportion of admissible numbers divisible by certain powers of the other $p_i$ invariant.
The number of strings whose product is not divisible by $p^k$ is the sum of the numbers of ways of distributing exactly $0$ to $k-1$ factors of $p$ over the $n$ elements. Of the $d$ possible values, a fraction $\left(1-\frac1{p_i}\right)p_i^{-\ell}$ have exactly $\ell$ factors of $p$ for $0\le\ell\lt k_i$. Thus, the number of strings whose product is divisible by $d$ is
$$ d^n\prod_i\left(1-\left(1-\frac1{p_i}\right)^n\sum_{j=0}^{k_i-1}\binom{n+j-1}jp_i^{-j}\right)\;. $$
For $d$ prime, this reduces to $d^n-(d-1)^n$, in agreement with your result.