# Understanding why the modular function part of Shor's algorithm is unitary

I've been struggling to understand the modular exponent bit of Shor's algorithm. My understanding is that it takes a register in the state $$\frac{1}{\sqrt{Q}}\sum_{k=1}^{Q-1} |k\rangle |0\rangle$$ to the state $$\frac{1}{Q}\sum_{k=1}^{Q-1} |k\rangle |f(k)\rangle$$ where $$f(k) = x^{k}$$ mod $$N$$. (Here, $$x$$ is the random integer found at the start of Shor's algorithm.)

My question is: Why is this operation unitary?

The critical thing, in this case, about a unitary operator is that it maps orthogonal states to orthogonal states (if $$\langle i|j\rangle=0$$, then $$\langle i|U^\dagger U|j\rangle=0$$, so the transformed vectors $$U|i\rangle$$ and $$U|j\rangle$$ are orthogonal). Now, you've defined what it must do for a set of states: $$|k\rangle|0\rangle\mapsto |k\rangle|f(k)\rangle.$$ Now, it should be clear that all of the outputs are orthogonal to all other ones, simply as a result of the different values of $$k$$. So, surely, it will be possible to define a unitary over all possible basis states.
Indeed, the one of the usual starting points is to define the action of the unitary as $$|k\rangle|y\rangle\mapsto \left\{\begin{array}{cc} |k\rangle|y+x^k\text{ mod }N\rangle & y (a second is to use $$|k\rangle|yx^k\text{ mod }N\rangle$$ on the top line). If we look at all possible $$y$$ and $$k$$, then we're looking at the whole basis. Again, different $$k$$s clearly give orthogonal vectors, independent of the value of $$y$$. Primarily, we have to check that $$\langle y+x^k\text{ mod }N|y'+x^k\text{ mod}N\rangle=0.$$ This must be true provided $$y-y'\text{ mod }N\neq0$$, which is true for cases $$y,y' and $$y\neq y'$$.