Question in the stage of the proof in Euler's theorem? In Euler's (number theory) theorem one line reads: since $d|ai$ and $d|n$ and $gcd(a,n)=1$ then $d|i$. I've been staring at this for over an hour and I am not convinced why this is true could anyone explain why? I have tried all sorts of lemma's I've seen before but I honestly just can't see it and I feel I'm going round in circles. Could someone just explain to me why it is making me feel stupid. Here is the full proof for context and I highlighted the lines I don't get. Thanks! (Also hcf=gcd as I know  that confuses some people.)

 A: Since $d|n$ and gcd$(a,n) = 1$ we must have gcd$(d,a) = 1$, since if $a$ and $d$ shared some common divisor, then $a$ and $n$ would share some common divisor. Now since $d|ai$ and gcd$(a,d) = 1$ , $d|i$. This last statement is a straight forward Theorem that says that if $d|bc$ and gcd$(d,b) = 1$ then $d|c$. Below is a proof: 
Since gcd$(d,b) = 1$, we can write $xd + yb = 1$ for integers $x$ and $y$. Multiplying both sides of this equation by $c$ we obtain $xdc + ybc = c$. Since $d|bc$, $bc = kd$ for some integer $k$. Substituting this into our above equation yields $xdc + ykd = c$. Thus $(xc + yk)d = c$ so $d|c$.  
A: Since $d \mid s_i$ and $d \mid n$, clearly $d \mid (s_i+An)$. And $s_i+An = ai$, so $d \mid ai$. (maybe you understood this, but it was highlighted).
So $d\mid ai$ and $d\mid n$. Now since $\gcd(a,n)=1$, $a$ and $n$ have no common factors, and also $a$ and $d$ have no common factors. That means that $d \nmid a$ and $\gcd(d,a)=1$. That lets us step from $d\mid ai$ to $d\mid i$.
A: Clearer: since $\,a\,$ and $\,i\,$ are  coprime to $\,n\,$ so too is their product $\,ai\,$ (by Euclid's Lemma). 
By the Euclidean algorithm $\ 1 = \gcd(ai,n) = \gcd(\color{#c00}{ai\bmod n},\,n) = \gcd(\color{#c00}{s_i},n).\,$ So $\,s_i\,$ is coprime to $\,n\, $ and $\,0\le s_i < n,\,$ hence $\,s_i\in S,\,$ by the definition of $\,S.$
