@Deadcode Let A=p^n. Suppose B'>B and C=A (mod B'-1). Since B'>B, it must have p as a factor, so A and B'-1 are coprime. Now we can divide by A: B=1 (mod B'-1). But B'>B, so B=1.

I feel like all of these questions could be easily answered with the use of a couple of carefully chosen Lemmas. But I just do whatever I first think of when I see the problem

@H.PWiz How do you get that "Since B'>B, it must have p as a factor"?

Well when A gets smaller, it can't keep all of its ps

Ah right

@H.PWiz There's something wrong here. B=1 is not always true.

The whole beauty of the A=p^n thing is that it lets you have any quotient.

Oh

After supposing B'>B?

I see what you're saying

it's a contradiction

proof by contradiction

Awesome, thanks!

@H.PWiz This new second shortened form of division has let me golf 9 bytes off "shift right by half a bit"... and that may just be the beginning. Haven't yet looked through the whole thing for opportunities.

Cool! I suppose it's not so common to divide by big numbers in regex.

@H.PWiz It's saving 141 bytes on Shift right by half a bit!