Thread: Coset conundrum
View Single Post
Old 2021-08-28, 16:11   #1
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

22·3·499 Posts
Default Coset conundrum

Let n > 2 be an integer, b an integer, 1 < b < n, gcd(b, n) = 1, gcd(b-1,n) = 1, and let h be the multiplicative order of b (mod n).

Let k be an integer, 1 <= k < n.

Let ri = remainder of k*b^(i-1) mod n [0 < ri < n], i = 1 to h.

A) Prove that \sum_{i=1}^{h}r_{i}\;=\;m\times n for a positive integer m.

B) Prove that m = 1 if and only if n is a repunit to the base b, and also that one of the ri is equal to 1.

Remark: The thread title refers to the fact that the ri form a coset of the multiplicative group generated by b (mod n) in the multiplicative group of invertible residues (mod n).

Part (B) as I stated it above is completely wrong. I forgot to multiply a fraction by 1.

There is, alas, no connection to n being a repunit to the base b, or to any of the ri being 1, as shown by the example b = 10, k = 2, n = 4649 .

Foul-up corrected in followup post.

Last fiddled with by Dr Sardonicus on 2021-08-29 at 13:21 Reason: xingif stopy
Dr Sardonicus is offline   Reply With Quote