I want to compute $ A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $j$ in $\Omega(\log j)$ airthmetic operations.
Easily we can compute set $A$ in $O(k \log k )$ airthmetic operations.
Question : How to compute set $A$ in $O(k)$ many arithmetic operations?