Frustrating step in a proof - basic abstract algebra

In summary, the conversation discusses a frustrating step in a proof related to information theory. The problem involves finding a proof for a function involving a pair of integers in a specific set. The conversation also mentions two claims, one that there are exactly P unique solutions and the other that each mapping possesses the same number of solutions in the given set. The conversation ends with the speaker requesting guidance in proving the claims.
  • #1
Chu
10
0
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.
 
Last edited:
Physics news on Phys.org
  • #2
And this is why we don't do math after 20 hours of no sleep :blushing: Just realized how (b) follows from (a).
 
  • #3


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.
 

1. What is the most common frustrating step in a proof in basic abstract algebra?

The most common frustrating step in a proof in basic abstract algebra is getting stuck or lost in the algebraic manipulations. Many students struggle with understanding which algebraic rules to apply and how to simplify expressions in order to reach the desired result.

2. How can I overcome frustration in this step?

One way to overcome frustration in this step is to practice and become familiar with the basic algebraic rules and properties. It is also helpful to break down the problem into smaller, more manageable steps and to work backwards from the desired result. Additionally, seeking help from a tutor or classmate can provide a fresh perspective and new approaches to the problem.

3. Are there any specific strategies that can make this step less frustrating?

Yes, there are several strategies that can make this step less frustrating. One strategy is to work on similar problems and practice using algebraic rules to manipulate expressions. Another strategy is to take breaks and come back to the problem with a clear mind. Additionally, seeking outside resources such as online tutorials or textbooks can provide alternative explanations and approaches for solving problems.

4. Is it normal to find this step frustrating?

Yes, it is completely normal to find this step frustrating. Abstract algebra can be a difficult subject for many students, and it often requires a lot of practice and patience. It is important to remember that frustration is a natural part of the learning process and that it is okay to struggle with certain concepts.

5. How can I stay motivated when facing frustration in this step?

Staying motivated can be challenging when facing frustration in this step, but it is important to remember why you are learning abstract algebra and the potential applications and benefits of mastering this subject. It can also be helpful to set small, achievable goals and to reward yourself for making progress. Finally, remind yourself that overcoming frustration and successfully completing a proof can be incredibly satisfying and rewarding.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
887
  • Linear and Abstract Algebra
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
995
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
963
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
1K
Back
Top