Define the function $f(n)=|A_n|-|B_n|$. Obviously $f(1)=1$. Let us notice that if $n$ is a positive integer divisible by a prime $p$, then $\gcd(x,n)$ and $\gcd(x+nk,pn)$ have the same prime factors for all $x$ and $k$. This means that if $x\in X_n$ it follows that $\{x,x+n,x+2n,...,x+(p-1)n\}\subset \{X_{np}\}$, where $X\in \{A,B\}$. It immediately results that $|A_{np}|=p|A_n|$ and $|B_{np}|=p|B_n|$, hence $f(np)=pf(n)$. Therefore it is sufficient to prove the assertion for $n=\displaystyle\prod_{i=1}^{s}p_i$, where $p_1,p_2,...,p_s$ are different prime numbers. Let's remark now that: $\bullet$ a number $x$ counts in $f(n)$ as $\mu(d)$, where $d=\gcd(n,x)$ and $\mu$ is Möbius function; $\bullet$ there are $\varphi(\frac nd)$ numbers $x$ that satisfy the property $d=\gcd(x,n)$. We obtain $f(n)=\displaystyle\sum_{d\mid n} \mu(d)\varphi(\frac nd)$. (and eventually we could get using Möbius inversion formula that $\varphi(n) =\displaystyle\sum_{d\mid n} f(d)$) Now a classical $PIE$ argument gives us: \[f(p_1\cdot p_2\cdot \ldots \cdot p_s)=(p_1-2)\cdot (p_2-2)\cdot \ldots \cdot(p_s-2)\]

For the last step in Lawasu's proof, we don't need anything as complicated as a PIE argument. The fact $ f(n) = \sum_{d \vert n}\mu(d)\phi\left(\frac{n}{d}\right) $ for squarefree $ n $ is clear and this function is clearly multiplicative since $ \mu $ and $ \phi $ are both multiplicative. Since $ f(p) = p - 2 $ for all primes $ p $ the desired result follows immediately.

$|A_n| - |B_n| = \prod (p_i-2) .\frac{n}{rad(n)}$

Took longer than expected:- We'll try finding a generalized formula for $|A_n|-|B_n|$ Let $\omega(n)$ denote the number of prime factors of $n$ without counting multiplicities. Note that $\omega(xy)=\omega(x)+\omega(y)$ when $\gcd(x,y)=1$ So,$|A_n|-|B_n|=\sum_{i=1}^{n-1} (-1)^{\omega(i)}$ Further for each $d|n$ there are exactly $\phi({\frac{n}{d}})$ integers with $\gcd(k,n)=d$ So the sum becomes $|A_n|-|B_n|=\sum_{i=1}^{n-1} (-1)^{\omega(d)} \phi({\frac{n}{d}})$ Clearly this is a convulution of two multiplicative functions,hence it is multiplicative so if suffices to check this for just $N=p^k$ Inputting $p^k$ we obtain $p^{k-1}(p-2)$ Hence $|A_n|-|B_n|=n \sum_{d|n} ({1-\frac{2}{d}})$,and the result follows.

I think DFT can triviliaze the problem!