Coset conundrum

[Dr Sardonicus]

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 r_i = remainder of k*b^(i-1) mod n [0 < r_i < n], i = 1 to h.

A) Prove that 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 r_i is equal to 1.

Remark: The thread title refers to the fact that the r_i 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 r_i being 1, as shown by the example b = 10, k = 2, n = 4649 .

Foul-up corrected in followup post.

[uau]

Originally Posted by Dr Sardonicus

A) Prove that for a positive integer m.

If you multiply the elements of the set {b^i for all i} by b, you get the same set with permuted elements. Thus multiplying the sum by b does not change it mod n. Thus S*b = S mod n, S*(b-1)=0 mod n, and S must be 0 mod n.

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

The "and also that one of the r_i is equal to 1" part seems ambiguous or wrong. For k != 1, m may or may not equal 1?

n = 1111, b = 10, k = 2: m = 1
n = 1111, b = 10, k = 21: m = 2

[Dr Sardonicus]

Originally Posted by uau

<snip>
The "and also that one of the r_i is equal to 1" part seems ambiguous or wrong. For k != 1, m may or may not equal 1?

n = 1111, b = 10, k = 2: m = 1
n = 1111, b = 10, k = 21: m = 2

Mea culpa. I made a huge blunder. Actual characterization of the multiplier m follows, proof left as exercise.

Conditions restated for ease of reference:

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.

(B) Let A = k*(b^h - 1)/n, and s_b(A) the sum of the base-b digits of A. Then m = s_b(A)/(b-1).