Number of solutions to congruence with additive gcd condition Let $l,l',q,d\in \mathbb N$ with $(l,l')=1$ and $d|q$ be given.  Define $g=(q,l)$ and $Q=q/g$; similarly define $g'=(q,l')$ and $Q'=q/g'$.  Denote by $C$ the conditions
\[ n'lg'\equiv nl'g\text { mod }(q)\]
\[ (ng+n'g',q)=d.\]
For a sum running up to a value $N\in \mathbb N$ denote by
\[ \sideset {}{'}\sum _{n=1}^N\]
the sum restricted to those $n$ with $(n,N)=1$.
How can I work out
\[ S_q(l,l'):=\sideset {}{'}\sum _{n=1}^Q\sideset {}{'}\sum _{n'=1\atop {C}}^{Q'}1?\]

What I can do:
If I suppose $l$ is coprime to $q$ (so that $g=1$) then the conditions $C$ are equivalent to the conditions
\[ n'g'\equiv nl'\overline l\text { mod }(q)\]
\[ (n+nl'\overline l,q)=d\]
which we'll denote by $D$, so that the sum in question is
\[ \sideset {}{'}\sum _{n=1}^Q\sideset {}{'}\sum _{n'=1\atop {D}}^{Q'}1.\]
The $n'$ sum has exactly one term if (remember $g'|l'$)
\[ (nl'\overline l/g',Q')=1\]
(which is equivalent to $(n,Q')=1$) and none otherwise, so that the above is equal to
\[ \sum _{n=1\atop {E}}^Q1\]
where $E$ denotes the conditions
\[ (n,Q)=1\]
\[ (n,Q')=1\]
\[ (n(l+l'),q)=d.\]
These are equivalent to (since $[Q,Q']=q$ as $(l,l')=1$)
\[ (n,q)=1\]
\[ (l+l',q)=d\]
so that the whole sum is zero if we don't have $(l+l',q)=d$, and if we do then the sum is
\[ \sum _{n=1\atop {(n,q)=1}}^Q1=\phi (q).\]
But I get quickly lost in the general case.
Any ideas?  I try to start by writing the sum as
\[ \sum _{N=1\atop {F}}^q\sideset {}{'}\sum _{n=1}^Q\sideset {}{'}\sum _{n'=1\atop {G}}^{Q'}1\]
where $F$ denotes the condition $(N,q)=d$ and $G$ denotes the conditions
\[ n'l/g\equiv nl'/g'\text { mod }(q/gg')\]
\[ ng+n'g'\equiv N\text { mod }q\]
and count solutions using the fact that the equations
\[ x\equiv a\text { mod }q\]
\[ x\equiv a'\text { mod }q'\]
have a unique solution modulo $[q,q']$ exactly when $(q,q')|a-a'$ and that this solution is coprime to $[q,q']$ exactly when $(a,q)=(a',q')=1$, but the sum still gets too complicated for me to see what's going on.
 A: Write $\tilde l=l+l'$ and $\tilde g=(q,\tilde l)$.  As said in the last bit of the question, we have
\[ S_q(l,l')=\sum _{N=1\atop {(N,q)=d}}^q\sideset {}{'}\sum _{n=1\atop {ng\equiv N\text { mod }(g')}}^Q\sideset {}{'}\sum _{n'=1\atop {n'l/g\equiv nl'/g'\text { mod }(q/gg')\atop {n'g'\equiv N-ng\text { mod (q)}}}}^{Q'}1.\]
The two equations are equivalent to one equation modulo $q/g'$ provided
\[ q/gg'|\frac {N-ng}{g'}-nl'/g'\overline {\frac {l}{g}}\iff q/g|(N-ng)\frac {l}{g}-nl'=-n\tilde l+Nl/g\]
and this solution is coprime to $Q'$ if and only if
\[ \left (\frac {N-ng}{g'},Q'\right )=\left (nl'/g'\overline {\frac {l}{g}},q/gg'\right )=1,\]
the second of which is automatic, so
\[ S_q(l,l')=\sum _{N=1\atop {(N,q)=d}}^q\sideset {}{'}\sum _{n=1\atop {ng\equiv N\text { mod }(g')\atop {n\tilde l\equiv Nl/g\text { mod }(q/g)\atop {((N-ng)/g',Q')=1}}}}^{Q'}1=\sum _{N=1\atop {(N,q)=d\atop {\tilde g|N}}}^q\sideset {}{'}\sum _{n=1\atop {ng\equiv N\text { mod }(g')\atop {n\tilde l/\tilde g\equiv Nl/\tilde gg\text { mod }(q/\tilde gg)\atop {((N-ng)/g',g\tilde g)=((N-ng)/g',q/gg'\tilde g)=1}}}}^{Q'}1=\sum _{N=1\atop {(N,q)=d\atop {\tilde g|N\atop {(N,g)=1}}}}^q\sideset {}{'}\sum _{n=1\atop {ng\equiv N\text { mod }(g')\atop {n\tilde l/\tilde g\equiv Nl/\tilde gg\text { mod }(q/g\tilde g)\atop {(N-ng,\tilde g)=1\hspace {2mm}(N-ng,q/g\tilde g)=g'}}}}^{Q'}1.\]
We have
\[ (n,Q)=1\iff (n,q/g\tilde g)=(n,\tilde g)=1\iff (Nl/\tilde gg\overline {\tilde l/\tilde g},q/g\tilde g)=(n,\tilde g)=1\iff (N/\tilde g,q/g\tilde g)=(n,\tilde g)=1\]
and
\[ N-ng\equiv N-\frac {Nl}{\tilde gg}\overline {\frac {\tilde l}{\tilde g}}g\equiv \frac {N}{\tilde g}\overline {\frac {\tilde l}{\tilde g}}\left (\tilde l-l\right )\equiv \frac {Nl'}{\tilde g}\overline {\frac {\tilde l}{\tilde g}}\text { mod }(q/g\tilde g)\]
so
\[ S_q(l,l')=\sum _{N=1\atop {(N,q)=d\atop {\tilde g|N\atop {(N,g)=1\atop {(N/\tilde g,q/g\tilde g)=1\atop {(Nl'/\tilde g,q/g\tilde g)=g'}}}}}}^q\sum _{n=1\atop {ng\equiv N\text { mod }(g')\atop {n\tilde l/\tilde g\equiv Nl/\tilde gg\text { mod }(q/g\tilde g)\atop {(N-ng,\tilde g)=1\atop {(n,\tilde g)=1}}}}}^{Q'}1=\sum _{N=1\atop {(N,q)=d=\tilde g}}^q\sum _{n=1\atop {ng\equiv N\text { mod }(g')\atop {n\tilde l/\tilde g\equiv Nl/\tilde gg\text { mod }(q/g\tilde g)\atop {(N-ng,\tilde g)=1\atop {(n,\tilde g)=1}}}}}^{Q}1=\sum _{N=1\atop {(N,q)=d=\tilde g}}^q\sum _{n=1\atop {ng\equiv N\text { mod }(g')\atop {n\tilde l/\tilde g\equiv Nl/\tilde gg\text { mod }(q/g\tilde g)\atop {(n,\tilde g)=1}}}}^{Q}1.\]
The two congruences have a unique solution modulo $q/g\tilde g$ provided
\[ g'|N\overline g-Nl/\tilde gg\overline {\frac {\tilde l}{\tilde g}}\iff g'|N\tilde l/\tilde g-Nl/\tilde g=Nl'/\tilde g\]
which is true, so the $n$ sum is for some $\rho $ with $(\rho ,q/g\tilde g)=1$ (since $(Nl/\tilde gg,q/g\tilde g)=1$)
\[ \sum _{n=1\atop {n\equiv \rho (q/g\tilde g)\atop {(n,\tilde g)=1}}}^Q1=\sum _{h|\tilde g\atop {(h,q/g\tilde g)|\rho }}\mu (h)\sum _{n=1\atop {hn\equiv \rho (q/g\tilde g)}}^{Q/h}1=\tilde g\sum _{h|\tilde g\atop {(h,q/g\tilde g)=1}}\frac {\mu (h)}{h}=\tilde g\prod _{p|\tilde g\atop {p\not |q/g\tilde g}}(1-1/p)\]
so
\[ S_q(l,l')=\tilde g\left (\sum _{N=1\atop {(N,q)=d=\tilde g}}^q1\right )\prod _{p|\tilde g\atop {p\not |q/g\tilde g}}(1-1/p)=\tilde g\phi (q/\tilde g)\prod _{p|\tilde g\atop {p\not |q/g\tilde g}}(1-1/p)=q\prod _{p|q/\tilde g}\prod _{p|\tilde g\atop {p\not |q/\tilde g}}.\]
Since
\[ \prod _{p|q}=\prod _{p|q\atop {p|q/\tilde g\hspace {2mm}p|\tilde g}}\prod _{p|q\atop {p|q/\tilde g\hspace {2mm}p\not |\tilde g}}\prod _{p|q\atop {p\not |q/\tilde g\hspace {2mm}p|\tilde g}}=\prod _{p|q/\tilde g}\hspace {3mm}\prod _{p|\tilde g\hspace {2mm}p\not |q/\tilde g}\]
the product is $\phi (q)/q$ so
\[ S_q(l,l')=\phi (q).\]
