Shuffling Cards (with a flip)

April 2023

Introduction–The Shuffling Problem #

Card shuffling is an important part of playing any card game. When a card deck isn’t shuffled properly, it leads to uneven and unfair distribution of cards. It would certainly help if you knew what cards other players had!

Suppose we have a specified shuffling algorithm. Is it possible for us to guess the outcome of the card shuffling? Is it possible that the card deck will at some point return to its original configuration? In a previous article we explored ways of trying to guess the outcome of a specific type of card shuffling, known as the riffle shuffle. In this article, we modify the shuffling algorithm to introduce a flip that introduces some interesting complexities.

The Standard Problem #

We may define a riffle shuffle, for a deck of an even number of cards, as a shuffle carried out by performing the following steps.

1. Split the card deck into two equal halves

2. Put the top half of the deck to the left and the bottom half of it to the right.

3. Take a card from the top of the deck on the left and put it down on the table

4. Take a card from the top of the deck on the right and put this card below the card that is already on the table

5. Repeat.

A well-known problem is: How many riffle shuffles will it take for the deck of $m$ cards to return to its original position? It turns out that the answer is the order of $2$ modulo $m$. Another problem that must in fact be answered in order to answer the previous question is: Given the current position of a card, what will be its position after a single riffle shuffle is performed? It turns out, that if we label the positions of the cards from $0$ to $m-1$, then the position of a card with current position $k$ after a single shuffle will be $2k \mod{m-1}$.

A Modification of the Problem #

A modification of the problem is as follows: While you are performing the riffle shuffle, suppose instead of putting down the cards as they are, you flip the cards from the right deck. Now, how many shuffles will it take for all cards in the deck to return to their original positions? What about the number of shuffles after which all cards will return to their original flip configuration? What is the relation between these two?

Visualizing the Process #

We shall start with visualizing the process of shuffling cards as described in the previous section. Let us start with an example of a deck of $8$ cards. Each card in the deck is unique. Initially, let the cards in the deck be labelled from $A$ to $H$ and be in alphabetical order. If a card $X$ is flipped, we shall denote it by the corresponding lower case letter $x$. So, the deck initially looks like as follows: $$\begin{matrix} A \\ B \\ C \\ D \\ E \\ F \\ G \\ H \end{matrix}$$ Let us now shuffle the deck. By our definition of a shuffle, we split the deck into two equal halves, and place the top half of the deck to the left and the bottom half deck to the right: $$\begin{matrix} A & E \\ B & F \\ C & G \\ D & H \end{matrix}$$

Now, as described before, we first put the card at the top of the left deck, $A$. Next, we take the card on top of the right deck, flip it over, and put it below card $A$. So we will have $e$ below $A$. We continue to repeat this process. Doing so, we finally get the following deck: $$\begin{matrix} A \\ e \\ B \\ f \\ C \\ g \\ D \\ h \end{matrix}$$ Notice that, as before the position of each card (when the positions are numbered from $0$ to $7$) is doubled modulo $7$ after performing a shuffle. The position of the last card in the deck remains $7$.
 
Our primary concern in this section is to find after how many shuffles the cards will all be unflipped. Based on our notation, this is the same as finding the number of shuffles after which every card in the deck is represented by an upper-case letter. We shall try to derive a relation between the number of shuffles it takes for the cards to all be flipped face-down, and the number of shuffles it takes to get the cards all back to their original position. We shall refer to the number of shuffles that it takes to get all cards back to flipping up the flip period and the number of shuffles it takes for all cards to get back to their original position the shuffle order.
 
In order to see a full picture of what is going on, let us continue shuffle our deck of $8$ cards. $$\begin{matrix} A & A & A & A & A & A & A \\ B & e & c & b & E & C & B \\ C & B & e & c & b & E & C \\ D & f & G & D & f & G & D \\ E & C & B & e & c & b & E \\ F & g & d & F & g & d & F \\ G & D & f & G & D & f & G \\ H & h & H & h & H & h & H \end{matrix}$$

When does a particular card, say card C for instance, get flipped? We see that card $C$ takes on the following positions: $2, 4, (1), (2), (4), 1, 2$. Here, $(a)$ denotes that the card is at position $a$ and is flipped, whereas $a$ denotes that the card is at position $a$ and is NOT flipped. This motivates an observation: A card gets flipped in the next shuffle, if its current position is greater than half of $7$ (where $7$ is the maximum position that a card may take, i.e. $m-1$ where $m$ is the number of cards in the deck). In other words, a card gets flipped in the next shuffle if it currently lies in the second half of the deck. Indeed, card $C$ gets flipped only when its position is $4$.
 
While this observation is significant, it does not require much effort to prove. It follows directly from how we are shuffling the cards. We flip only the second half of the deck, which proves this observation.
 
So now, how do we determine whether a particular card is flipped or not, given the number of cards in the deck and the number of times that the deck has been shuffled? Let us again take an example. Consider a deck of $8$ cards as earlier. Suppose the deck is shuffled $5$ times. What is the orientation of card $C$? Is it flipped face-down or face-up? We see that the position of card $C$ after $5$ shuffles is $1$ and it is not flipped (or face-up). When the deck is shuffled $4$ times, card $C$ is flipped and is at position $(4)$. Card $C$ is flipped after $2, 3$ and $4$ shuffles, whereas it is not flipped after $0, 1, 5$ and $6$ shuffles.
 
Is there a general pattern? Note that a card will be flipped face-down if the number of times it gets flipped during the process of shuffling is even, and will be face-up if the number of times it gets flipped during the process is odd. This indeed does hold for card $C$. Now, since a card is flipped when it lies in the second half of the deck, this implies that a card is face-up when the number of times it lies in the second half of the deck before the $k$the shuffle is odd, where $k$ is the number of shuffles.
 
For example, let $k=5$. Card $C$ lies in position $4$ twice before the fifth shuffle takes place. Therefore, $C$ is face-down after $5$ shuffles.
 
Let $k=4$. Card $C$ lies in position $4$ only once before the fourth shuffle. Thus, the card is flipped face-up.
 
In general, we may conclude that, for a deck of $m$ cards, a given card is flipped after $k$ shuffles if and only if the number of times its position is greater than $(m-1)/2$ before the $k$th shuffle takes place is odd. In other words, consider a deck of $m$ cards. Consider some card in the deck, $X$. Let the position of card $X$ after $i$ shuffles be $a_i$. Card $X$ is flipped after $k$ shuffles if and only if the number of values of $a_i$ that are greater than $(m-1)/2$ as $i$ goes from $0$ to $k-1$ is odd.
 
Now, let us explore the relation between the flip period and the shuffle order. Notice that the shuffle order for $8$ cards is $3$, whereas the flip period is $6$. Notice how the shuffle order divides the flip period. Does this always hold? Indeed, using a computer program, one may observe that the flip period is always a multiple of the shuffle order. We shall in the rest of the article, try to prove this.

Mathization #

In this section we shall focus on making the process more mathematical in order to make it easier to prove our observations. Before doing so, we shall introduce a modified division algorithm in order to motivate future steps.

Theorem 1. For positive $a$ and $p$ that are integers, there exist integers $q, r$ and $\epsilon$ such that $a = pq + \epsilon r$ where $0 \leq r \leq \frac{p}{2}$ and $\epsilon = \pm1$.

We shall prove this result later. We will explain what the result states in more detail and move directly to its application to our card shuffling problem.
 
The ordinary division algorithm states that for every $a, p$ that are positive integers, there exist integers $q$ and $r$ such that $a = pq + r$ and $0 \leq r < p$. However, our new division algorithm takes this a step further. Our new division algorithm further restricts the possible values of the remainder to just $0 \leq r \leq p/2$. However, in order to ensure that this division algorithm holds for all integer, it is necessary to introduce a variable $\epsilon$ that is either $+1$ or $-1$. Another way to think of the difference between the two division algorithms is as follows: The quotient obtained by the ordinary division algorithm yields the greatest integer that is less than or equal to $a/p$. On the other hand, our modified division algorithm not only floors the result of $a/p$, but rounds it off to the nearest integer.
 
Let us also introduce new notation equivalent to mod for our new division algorithm. Let $a\mkern{3mu}{\mathrm{mmod}}\mkern{3mu}p$ denote the remainder, $\epsilon r$ obtained when $a$ is divided by $p$ using our modified division algorithm. So, we have $13\mkern{3mu}{\mathrm{mmod}}\mkern{3mu}5 = -2$ whereas $13 \mod 5 = 3$.
 
How does all of this relate to our problem? We earlier concluded that a given card is flipped after $k$ shuffles if and only if the number of times it was in the second half of the deck before the $k$th shuffle is odd. Notice how our new division algorithm gives us a neat way to tell when a card is in the second half of the deck. If the position of a card mmod $p$ where $p = m-1$ is positive, then the card is in the first half of the deck. If it is negative, it is in the second half of the deck. For example, consider a deck of $8$ cards. We want to check if the position $4$ corresponds to the first half of the deck or the second half of the deck. Since $4 \mkern{3mu}{\mathrm{mmod}}\mkern{3mu}7 = -3$, it is in the second half of the deck.
 
We may thus reframe our condition for a card to be flipped as follows: In a deck of $p+1$ cards, a card is flipped after $k$ shuffles, iff the number of times its position in the deck mmod $p$ is negative before $k$ shuffles have taken place, is odd. We may also state it as: consider a deck of $m$ cards. Consider some card in the deck, $X$. Let the position of card $X$ after $i$ shuffles be $a_i$. Card $X$ is flipped after $k$ shuffles if and only if the number of values of $a_i$ that are negative mmod $p$ as $i$ goes from $0$ to $k-1$ is odd. For example, let us reconsider the deck of $8$ cards and the card $C$. The position of card $C$ mmod $7$ is given as: $2, -3, 1, 2, -3, 1, 2$. There are two negative values before $5$ shuffles have taken place. Hence $C$ is not flipped after $5$ shuffles. There is only one negative value before $4$ shuffles. Thus, $C$ is flipped after four shuffles.
 
However, none of what we have done till now makes the problem significantly easier to solve. Instead of saying the number of times the position of the card is greater than $p/2$, we simply said the number of times its position mmod $p$ is negative. This does not make any difference but convenience. It does not make it any clearer as to how one could proceed to prove that the flip period is a multiple of the shuffle order. In order to make full use of our new division algorithm and notation, we need another important result. We need something that will help us identify when a card will have a negative position.

Theorem 2. Let $a, p, q, r$ and $\epsilon$ be integers (with $a$ and $p$ positive) such that $a = pq + \epsilon r$. Then $\epsilon = (-1)^{\left\lfloor 2a/p \right\rfloor}$.

Again, we shall for now focus more on the application of the above theorem and leave the proof to the end. How do we use this theorem? Let the position of a card in the deck be $a$. By the above theorem, we have that the card is in the second half of the deck if and only if $\left\lfloor 2a/p \right\rfloor$ is odd. For example, if the position of card $X$ is $a=4$ in a deck of $8$ cards, then it lies in the second half of the deck since $\left\lfloor 2a/p \right\rfloor = 1$. On the other hand, $\left\lfloor 2\cdot 3/7 \right\rfloor = 0$ and therefore the card at position $3$ lies in the first half of the deck.
 
We may thus state our result regarding the flip of a card finally as follows: Consider a deck of $p+1$ cards. Consider a card $X$ in the deck. Let the position of $X$ after $i$ shuffles be given by $a_i$. Then, the card $X$ is flipped after $k$ shuffles if and only if the number of times $\left\lfloor 2a_i/p \right\rfloor$ is odd as $i$ goes from $0$ to $k-1$ is odd.
 
Till now, all we did was state the same result that we observed in the very first section in different ways, some in fact more complicated. How does this help in any way? Let us try to use what we know from the already solved problem of shuffle order. We know that if the position of card $X$ is initially $a$, then its position after $i$ shuffles is given by $2^ia \mod p/2$. So, in a deck of $p+1$ cards, if $a$ is the initial position of a card $X$, then its position will proceed as follows, till $k$ shuffles: $$a, 2a, 2^2a, \dots, 2^ka \pmod{p/2}$$ We also know that the card $X$ will be flipped after $k$ shuffles if the number of times the position is greater than $p/2$ is odd. We may equivalently say that: the card $X$ will be flipped if the number of times $\left\lfloor 2a_i/p \right\rfloor$ is odd, is odd. We saw this in the previous section.
 
But the former way of stating it sounded much simpler. Why did we introduce the latter way of putting it in the first place? It seems to only make it more complicated. However, when one tries to solve the problem of finding the number of times $2^ia\mod p$ is greater than $p/2$, it is not so easy. So, let us see how lucky we get with the latter, more complicated form.
 
Since $a_i = 2^ia$, $\left\lfloor 2a_i/p \right\rfloor = \left\lfloor 2^{i+1}a/p \right\rfloor$ where $a$ is the initial position of $X$. Thus, $X$ is flipped if and only if the number of times $\left\lfloor 2^{i+1}a/p \right\rfloor$ is odd, is odd. In case this sounds confusing, let us go back to our example of a deck of $8$ cards. The initial position of card $C$ is $2$. The values of $\left\lfloor 2^{i+1}a/p \right\rfloor$ are therefore: $$\left\lfloor 2\cdot 2/7 \right\rfloor, \left\lfloor 4\cdot 2/7 \right\rfloor, \left\lfloor 8\cdot 2/7 \right\rfloor, \left\lfloor 16\cdot 2/7 \right\rfloor, \left\lfloor 32\cdot 2/7 \right\rfloor, \left\lfloor 64\cdot 2/7 \right\rfloor, \left\lfloor 128\cdot 2/7 \right\rfloor$$ which is equal to $$0, 1, 2, 4, 9, 18, 36$$ Suppose $5$ shuffles are performed. The number of values that are odd before 5 shuffles are performed is $2$. Thus, the card is not flipped after five shuffles, whereas it is flipped after four.
 
Now, for the sake of convenience, let us introduce a new notation. Consider a positive real number $n$ and the list $S_n [\left\lfloor n \right\rfloor, \left\lfloor n/2 \right\rfloor, \left\lfloor n/4 \right\rfloor, \dots, 0]$. We shall say $\xi(n) = 0$ if the number of odd elements of the list is even, and $\xi(n) = 1$ if the number of odd elements of the list is odd. How does this relate to our problem? Suppose we let $n=2^ka/p$. Then, the corresponding list will be $[\left\lfloor 2^ka/p \right\rfloor, \left\lfloor 2^{k-1}a/p \right\rfloor, \dots, 0]$. This list is equivalent to the list of $\left\lfloor 2a_i/p \right\rfloor$ as $i$ ranges from $0$ to $k-1$. Hence, if the number of odd elements in this list is odd, then the card $X$ will be flipped. In other words, card $X$ will be flipped if $\xi(2^ka/p) = \xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 1$. Similarly, it will not be flipped it $\xi(\left\lfloor 2^ka/p \right\rfloor = 0)$.
 
Therefore, we may now conveniently say that in a deck of $p+1$ cards, a card $X$ with initial position $a$ is flipped after $k$ shuffles if and only if $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 1$.

Flip Period and Shuffle Order #

Until now, the only thing we did was to give a nice mathematical way of saying when a card is flipped, purely using notations. We shall now use it in order to prove our observed relation between shuffle order and flip period. Let us represent the shuffle order of a deck of $p+1$ cards as $\mathop{\mathrm{ord}}(p)$ and the flip period of a deck of $p+1$ cards as $\mathop{\mathrm{ford}}(p+1)$. We know that $\mathop{\mathrm{ord}}(p)$ equals the order of $2$ modulo $p$. We shall now use these facts to prove the relationship we observed.
 
Firstly, let us get an idea of what the flip period is, as we have not discussed it in detail till now. The shuffle flip period is the number of shuffles that it takes for all cards in the deck to revert to their original configuration in terms of flips. In other words, the smallest number of shuffles it takes for all cards to be facing down again. We know that for a card $X$ with initial position $a$ to be facing down after $k$ shuffles, we must have $$\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 0$$ Now, we are dealing with the case when ALL cards in the deck face down. Therefore, for every card in the deck, the above must hold, where $a$ is the card’s respective starting position. In other words, for all $a$ from $0$ to $p-1$, we must have the above being true. The smallest positive $k$ for which this is satisfied will yield the flip period. In order to show that $\mathop{\mathrm{ord}}(p) \vert \mathop{\mathrm{ford}}(p)$, it will suffice to show that when $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 0$ for all $a$ from $0$ to $p-1$, then $2^k \equiv 1 \pmod{p}$. This will imply that $\mathop{\mathrm{ord}}(p)$ divides $k$ and hence that $\mathop{\mathrm{ord}}(p) \vert \mathop{\mathrm{ford}}(p)$ since $\mathop{\mathrm{ford}}(p)$ just represents the smallest such $k$. ¹
 
Let us first formulate a strategy. We want to prove that if $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 0$ for all $a$ from $0$ to $p-1$, then $2^k$ is $1$ mod $p$. Note the emphasis on all. Let us start with the assumption that $2^k$ is not 1 mod $p$. Then, even if we could prove that there exists just one value of $a$ from $0$ to $p-1$ that does not satisfy $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 0$, we would be done with our proof. Since it holds for all $a$, it must also hold for $a = 1$. Hence, $\xi\left(\left\lfloor 2^k/p \right\rfloor\right) = 0$. Given this, is it possible to find some value of $a$ such that $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 1$? What is $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right)$ in terms of $\xi\left(\left\lfloor 2^k/p \right\rfloor\right)$?
 
Before moving on, let us first explore a simple property of the $\xi$ function and another result.

Proposition 1. If $\xi(n) = 0$ then $\xi(2^in) = 0$ for any nonnegative integer $i$.

This is easy to prove. We are given that the number of odd elements in the list $S_n$ is even. The list $S_{2^in}$ is merely the list $S_n$ plus the elements $2^in, 2^{i-1}n, \dots, 2n$. All of these are even. Thus there are no more odd elements being added to $S_n$. Hence the result is proven.
 
Now, if $n$ is even and $\xi(n) = 0$, then what can we say about $\xi(n+1)$? Clearly, all elements of $S_{n+1}$ are the same as that of $S_n$, except for the last element, i.e. $n+1$. Since $n$ is even, $n+1$ is odd. Therefore, $\xi(n+1) = 1$.
 
Now how may we use this in our proof? We start with the fact that $\xi\left(\left\lfloor 2^k/p \right\rfloor\right) = 0$. Then, we know that if $a = 2^x$ for some nonnegative integer $x$, we have $\xi\left(a\left\lfloor 2^k/p \right\rfloor\right) = 0$. It follows that $\xi\left(a\left\lfloor 2^k/p \right\rfloor + 1\right) = 1$.
 
How does this help? So we did find something that yields $1$ when it is operated on by the $\xi$ function. But we need to find something of the form $\left\lfloor 2^ka/p \right\rfloor$. So, what if $$\left\lfloor 2^ka/p \right\rfloor = a\left\lfloor 2^k/p \right\rfloor + 1$$ Then, clearly $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 1$ and we have found our desired value of $a$. But does there always exist such a value of $a$ which both satisfies the above and the fact that $a = 2^x$? It turns out that such an $a$ does not always exist. So our attempt at proving our observation failed. Can we however salvage this? Indeed, the following result gives us some hope:

Proposition 2. Let $p, q$ be integers, with $p>q>1$. There exists some even integer $a$ such that $$\left\lfloor \frac{aq}{p} \right\rfloor = a\left\lfloor \frac{q}{p} \right\rfloor + 1$$ and $a < p$.

We shall prove the above proposition at the end along with other results that we have left out. We will be more concerned regarding how we may apply this to our problem.
 
The propoosition implies that for every $p$, if $2^k$ is not $1$ mod $p$, then there exists some even integer $a$ that is between $0$ and $p-1$ such that $$\left\lfloor \frac{2^ka}{p} \right\rfloor = \left\lfloor \frac{2^k}{p} \right\rfloor a + 1$$ Let us try to use this fact. Since $a$ is even, let $a = 2^xb$ where $b$ is odd. Given the above and that $x \neq 0$, what can we say about $\left\lfloor 2^kb/p \right\rfloor$? Observe that $$\left\lfloor \frac{2^kb}{p} \right\rfloor = \left\lfloor \frac{2^k}{p} \right\rfloor b$$ Again, we will prove this later, and will be concerned regarding its application. We may write $$\left\lfloor \frac{2^ka}{p} \right\rfloor = \left\lfloor \frac{2^k}{p} \right\rfloor a + 1 = 2^x\left\lfloor \frac{2^k}{p} \right\rfloor b + 1$$ Since $\left\lfloor 2^kb/p \right\rfloor = b\left\lfloor 2^k/p \right\rfloor$ we may therefore write the above as $$2^x\left\lfloor \frac{2^kb}{p} \right\rfloor + 1$$ Now, since $b<a$ it clearly lies between $0$ and $p$. It follows that $\xi\left(\left\lfloor 2^kb/p \right\rfloor\right) = 0$. Hence, as we have seen earlier $$\xi\left(\left\lfloor \frac{2^kb}{p} \right\rfloor + 1\right) = \xi\left(\left\lfloor \frac{2^ka}{p} \right\rfloor\right) = 1$$ But $a$ lies between $0$ and $p-1$. This means that the card deck is not shuffled! This contradicts our assumption that $2^k$ is not $1$ mod $p$. Therefore, we must have $2^k \equiv 1 \pmod{p}$. This completes our proof!

Completing Proofs #

Proposition 3. Let $p, q$ be integers, with $p>q>1$. There exists some even integer $a$ such that $$\left\lfloor \frac{aq}{p} \right\rfloor = a\left\lfloor \frac{q}{p} \right\rfloor + 1$$ and $a<p$.

Proof. Let $q = pq’ + r$. So, $q’ = \left\lfloor \frac{q}{p} \right\rfloor$ and $0 \leq r < p$. We shall consider two cases as follows:

1. When $r > p/2$

2. When $r \leq p/2$.

When $r>p/2$, we may multiply both sides of $q = pq’ + r$ by $2$ to get $$2q = p(2q’) + 2r$$ Since $p/2 \leq r < p$, it follows that $p < 2r < 2p$. Hence, $$\left\lfloor \frac{2q}{p} \right\rfloor = 2q’ + 1 = 2\left\lfloor \frac{q}{p} \right\rfloor + 1$$ Thus, there always exists a value of $a$ satisfying the required conditions, i.e. $a=2$, when $r>p/2$.
 
Now, we come to the case when $r \leq p/2$. Let $a_0$ be the smallest possible value of $a$ that is even such that $a_0r \geq p$. We want to prove that $a_0r < 2p$. In order to do so, assume for the sake of contradiction that $a_0r \geq 2p$. Now, consider $a = a_0 - 2$. We have $$(a_0-2)q = p(a_0-2)q’ + (a_0-2)r$$ Since $0 \leq r \leq p/2$ and $a_0r \geq 2p$, it follows that $p \leq(a_0-2)r$. This contradicts our assumption that $a_0$ is the smallest even value of $a$ for which $a_0r \geq p$ since we have found a smaller value, i.e. $a-2$. Thus, we must have $p \leq a_0r < 2p$.
 
Now, $$a_0q = p(a_0q’) + a_0r$$ Since $p \leq a_0r < 2p$, $$\left\lfloor \frac{a_0q}{p} \right\rfloor = a_0\left\lfloor \frac{q}{p} \right\rfloor + 1$$ This shows that there exists some even $a$ such that $\left\lfloor aq/p \right\rfloor = a\left\lfloor q/p \right\rfloor + 1$ when $r \leq p/2$. Since we also showed the same for $r > p/2$, it holds valid regardless of the value of $r$. This completes our proof. ◻

Proposition 4. Let $a$ be even such that $\left\lfloor 2^ka/p \right\rfloor = \left\lfloor 2^k/p \right\rfloor a + 1$. Let $a = 2^xb$. Then, $\left\lfloor 2^kb/p \right\rfloor = \left\lfloor 2^k/p \right\rfloor b$.

Proof. Let $2^k = pq + r$ where $0 \leq r < p$. In other words, $\left\lfloor 2^k/p \right\rfloor = q$. Now, if we multiply both sides by $a$, we get $2^ka = p(aq) + ar$. It follows that $$\left\lfloor \frac{2^ka}{p} \right\rfloor = aq + \left\lfloor \frac{ar}{p} \right\rfloor = \left\lfloor 2^k/p \right\rfloor a + \left\lfloor \frac{ar}{p} \right\rfloor$$ since $q = \left\lfloor 2^k/p \right\rfloor$. We are also given that $\left\lfloor 2^ka/p \right\rfloor = \left\lfloor 2^k/p \right\rfloor a + 1$. Thus, $$\left\lfloor \frac{ar}{p} \right\rfloor = 1$$ This implies that $$p \leq ar < 2p$$ Now, let $a = 2^xb$. Since $a$ is even, $x\neq 0$. Dividing the above inequality by $2$ we therefore get $$\frac{p}{2} \leq 2^{x-1}br < p$$ It follows that $br < p$. Thus, $$\left\lfloor \frac{2^kb}{p} \right\rfloor = \left\lfloor \frac{2^k}{p} \right\rfloor b$$ which proves the desired result. ◻