Frustrating step in a proof - basic abstract algebra

[Chu]

Frustrating step in a proof -- basic abstract algebra

Hello all, I am trying to work on a proof related to information theory, and I have gotten stuck. I am nearly 100% this is true, but it might not be . . . and I am having trouble coming up with a proo for it in any case!
----------

M exist in Z_p, and we choose a pair of integers {a,b} also in Z_p, and a != 0. We then calculate E s.t.

E = a*M + b mod p.

Now, here is the ticky part (at least for me). If we consider the pair E and M generated by this function, it's pretty obvious that because of generative nature of mod p we could have chosen a different {a,b} pair and gotten the same solution.

What I am trying to show, is that given all {E,M} pairs, there are

(a) exactly P unique solutions (seems easy, consider the case of a = 1, generate all the solutions by varying b, and then use the birthday property to show that each other solution must map into one of the previously discovered mappings)

and the tricky one . . .

(b) Each E->M mapping possesses the same number of solutions in {a,b}

Can anyone nudge me in the right direction? As I said I'm nearly 100% sure that (b) is true because of corrarlies in the affine cryptosystem, but I am having a devil of a time proving it.

 

[Chu]

And this is why we don't do math after 20 hours of no sleep Just realized how (b) follows from (a).

 

[M98Ranger]

Hello there,

I understand your frustration with this step in your proof. Abstract algebra can often be challenging and require a lot of patience and careful reasoning. It seems like you have a good grasp on the problem and have made some progress, but just need some guidance on how to approach the tricky part.

Firstly, I would suggest reviewing the definitions and properties of mod p and how it affects the solutions of the equation E = a*M + b mod p. This might help you see the underlying pattern in the solutions and how they relate to each other.

Additionally, you could try considering the relationship between the solutions of E and M in terms of modular arithmetic. In particular, you could look at the relationship between the solutions of E and M in terms of their remainders when divided by p. This might provide some insight into why each E->M mapping has the same number of solutions in {a,b}.

Lastly, you could try using proof by contradiction to show that if (b) were not true, it would lead to a contradiction. This could help you see the logical flaw in your reasoning and guide you towards the correct proof.

I hope these suggestions help and wish you the best of luck in your proof. Abstract algebra can be frustrating at times, but keep persevering and I'm sure you'll be able to solve it.