Puzzle - RPL and others

[Albert Chan]

I was a bit confused about proof of gcd(2n,d) buckets, perhaps this help.

Let base n = p*m, where p is power-of-2, m is odd, m > 1

d_2p-1 * n + d_2p ≡ 0 (mod 2p)
d_2p ≡ (-p*m) * d_2p-1 (mod 2p)
d_2p / p ≡ -m * d_2p-1 (mod 2) = 1 (mod 2)
d_2p ≡ p (mod 2p)      

→ d_2p ≡ d_4p ≡ d_6p ≡ ... ≡ p (mod 2p)

d_p-1 * n + d_p ≡ 0 (mod p)
d_p ≡ (-p*m) d_p-1 = 0 (mod p)

→ d_1p ≡ d_3p ≡ d_5p ≡ ... ≡ 0 (mod 2p)       // p (mod 2p) were already taken

Instead of written in modulo form, we write the possible cases (we just don't know the order)
(note: m is odd, so m-1 is even, m-2 is odd ...)

d_2p, d_4p, d_6p ... d_(m-1)p  =  1p, 3p, 5p ... (m-2)p
d_1p, d_3p, d_5p ... d_(m-2)p  =  2p, 4p, 6p ... (m-1)p

Note indexes on the left does not match the possible values on the right.
But, if we swap the values (thru another indirection), both side matches.
Thus, we need to swap split buckets.

---

What happen if we extend this to gcd(4n, d) ?

d_4p-1 * n + d_4p ≡ 0 (mod 4p)
d_4p ≡ (-p*m) * d_4p-1 (mod 4p)
d_4p / p ≡ -m * d_4p-1 (mod 4) = ±1 (mod 4)
d_4p / p ≡ 1 (mod 2)
d_4p ≡ p (mod 2p)

Unfortunately, this is the same result from gcd(2n, d) buckets.