This question is from An Introduction to Quantum Computing Kaye et al. I'm having a difficult time coming up with a solution for this question. It is in relation to period finding however I cannot provide much more context than that. Any help is appreciated.
Suppose you are given the state $|\phi_{r,b}\rangle$ and a candidate $r^{'}$. Devise a '1-sided' test, which always outputs 0 if $r^{'}$ is a multiple of $r$, and outputs 1 with probability at least 50% otherwise.
Hint: What happens if we add $r^{'}$ mod $mr$ to the basis states of $|\phi_{r,b}\rangle$?
For reference: $$|\phi_{r,b}\rangle = \frac{1}{\sqrt{m}}\sum^{m-1}_{z =0}{|zr+b\rangle}$$ Where $b$ is chosen uniformly at random from $\{0,1,...,r-1\}$
