Let $n,k$, $1\le k\le n$ be fixed integers. Alice has $n$ cards in a row, where the card has position $i$ has the label $i+k$ (or $i+k-n$ if $i+k>n$). Alice starts by colouring each card either red or blue. Afterwards, she is allowed to make several moves, where each move consists of choosing two cards of different colours and swapping them. Find the minimum number of moves she has to make (given that she chooses the colouring optimally) to put the cards in order (i.e. card $i$ is at position $i$).

NOTE: edited from original phrasing, which was ambiguous.
1. **Graph Representation and Cycle Formation:**
   - Consider a directed graph where each vertex represents a card position from \(1\) to \(n\).
   - Draw a directed edge from vertex \(i\) to vertex \(j\) if the card at position \(i\) has the label \(j\). Specifically, \(j = i + k\) (or \(j = i + k - n\) if \(i + k > n\)).
   - Each vertex has an indegree of 1 and an outdegree of 1, forming disjoint cycles.

2. **Initial and Final Cycle Count:**
   - Initially, the graph has \(\gcd(n, k)\) cycles. This is because the number of cycles in such a permutation graph is given by the greatest common divisor of \(n\) and \(k\).
   - The goal is to have each card in its correct position, which corresponds to having \(n\) cycles (each card in its own cycle).

3. **Swapping Cards and Cycle Dynamics:**
   - When two cards of different colors are swapped, if they belong to different cycles, the cycles merge.
   - If they belong to the same cycle, the cycle splits into two.
   - Each swap can increase the number of cycles by at most 1.

4. **Minimum Number of Moves:**
   - Initially, there are \(\gcd(n, k)\) cycles.
   - To achieve \(n\) cycles, we need to increase the number of cycles by \(n - \gcd(n, k)\).
   - Therefore, at least \(n - \gcd(n, k)\) moves are required.

5. **Optimal Coloring and Achieving the Goal:**
   - Color the cards such that cards labeled \(1, 2, \ldots, \gcd(n, k)\) are blue and the rest are red.
   - In each cycle, there will be exactly one red card.
   - For each cycle, continuously swap the red card with the card it points to. This will remove one blue vertex each time.
   - Each cycle will require \(\frac{n}{\gcd(n, k)} - 1\) moves to sort completely.
   - Summing over all cycles, the total number of moves required is \(n - \gcd(n, k)\).

\(\blacksquare\)

The final answer is \( \boxed{ n - \gcd(n, k) } \).