is there any hope?

[faint crypt]

My attempt and the solution below. I understand the solution completely. But I dont understand why my approach lead me to have an incorrect answer. My proof writing is atrocious, aand If I were to be presented another simple proof it would probably be convoluted asf like this one. How do I avoid this?

[fringe condor]

1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
2. Wait patiently for a helper to come along.
3. Once someone helps you, say thank you and close the thread with:

   +close
   

4. Feel free to nominate the person for helper of the week in #helper-nominations
5. Do not ping the mods, unless someone is breaking the rules. If there is a conflict amongst multiple helpers feel free to ping “Helper Mod”
6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[candid hedge]

are you familiar with Bezout's identity ?

(the proof you wrote makes no sense)

(or Gauss Lemma, one of these two will suffice)

[faint crypt]

Yes, idk how to use it.

[candid hedge]

ok, bezout's identity states that if a and b are coprime (that is (a,b) = 1), then there exists two integers u and v such that au + bv = 1.

in your case, you know that (a,n)=1, so you may write au + nv = 1 for some integers u and v

[faint crypt]

Do i use bezouts identity anytime i see gcd in a proof?

[candid hedge]

no, it is not automatic, but you it should switch some light on

now, you use the information that n divides ab, so you want to make ab appear somewhere in the bezout identity

[candid hedge]

(or maybe it is better to take Bezout's identity and you look at it mod n @faint crypt )

[faint crypt]

If 1=gcd(a,b) then doesnt a=1 by definition? We can represent a by its coefficient 1 hence n|(b-c)?

[candid hedge]

no, 1=gcd(a,b) means that any integer that divides both a and b must also divide 1

for instance, gcd(3,5)=1

indeed, 5×2 - 3×3 = 1, so if d divides both 5 and 3, then d must divide the right hand-side of the equation, hence d divides 1

[faint crypt]

Can we write another pair of arbitrary variables to + to au+bv and use algebra to cancel (without dividing)? Im sort of lost.

[candid hedge]

just take the identity au+nv=1 modulo n, what do you observe ?

[faint crypt]

n|((au+nv)-1)

[candid hedge]

but n also divides nv, so what do you also conclude ?

[faint crypt]

This is where im not sure. But ill guess... maybe that n|bv as well? Since its of the form au+bv=1 which is equivalent?

[candid hedge]

there's no b yet, you simply started with (a,n) = 1, hence you have au + nv = 1 for some u and v

as n divides nv, what can you say about au - 1 ?

[faint crypt]

That b also divides that?

[candid hedge]

there's no b

I am just asking you to determine au-1 mod n

[faint crypt]

Sorry i meant n divides it too

[candid hedge]

ok, so au = 1 mod n.

now you go back to the equation ab = ac mod n