/sci/ - Science & Math

>>12525523
It’s not just a theorem. It’s the study of primitive roots.

>>12525550
i should have used the word result instead of theorem. does the result have a particular name associated with it? i assume it should given how many times i've seen it used in other proofs

>>12525523
follows from Bezout's identity

generator of cyclic group is coprime with order

>>12525523
It follows from Bezout's Identity, as this anon has pointed out >>12525570

In group theoretic language, you have what this guy has pointed out. Unfortunately, I don't think this idea has a catchy name like Bezouts identity.

>>12525550
WRONG. This is NOT about primitive roots. >>12525523
It's called Bezout's theorem. It uses ideals and IMO the standard proof is quite unsatisfactory. It's not something that feels natural.
The proof boils down to checking that for a,b coprime, the set {ak+bl | k,l integers} is the whole set, or equivalently, contains 1.The way you do it is by noting that the set is generated by its smallest positive member, which is a divisor of both a and b, so it must be 1.
If anyone knows a prettier proof I'd love to see it.

>>12525523

>>12525705
>>12525703
What do you think

>>12525935
>clearly we have x,y, integers with nx+ky=1
This is the heart of the proposition and the thing I said I've never seen a nice proof of.
Can you prove it in a nice way?

>>12525705
>>12525570
>>12525685
thanks! a bit terse, but i follow

>>12525982
found a pretty decent elementary proof on video here. it does not invoke repeating the Euclidean algorithm:
https://www.youtube.com/watch?v=E_mU_fCmcxc

>>12525982
>Can you prove it in a nice way?
Also, you can prove it with the concept of Principal ideal domain and common divisor.
But a bit too general.

>>12525982
You can prove it constructively by keeping track of what you've done in the Euclidean algorithm. At each step, each of the two numbers is a linear combination a(n)x + b(n)y, c(n)x + d(n)y of the original numbers x and y. The sum of the numbers decreases at each step until one of the numbers is zero, at which point the algorithm terminates, so the algorithm must terminate.

To prove the result of the algorithm is the gcd: We can prove the result is a common divisor by stepping backwards through the steps and seeing that the numbers at each step are multiples of the result. And knowing the result is a linear combination of the original numbers, it must be the greatest common divisor because any greater common divisor of x and y would have to divide ax+by.

To illustrate, say we're finding the gcd of 35 and 45.

35=1*35+0*45 | 45 = 0*35+1*45
35=1*35+0*45 | 10 = -1*35+1*45
5=4*35-3*45 | 10 = -1*35+1*45
5=4*35-3*45 | 0 = -9*35+7*45

>>12525523
Won, Toward, Tree, For, FiVe, Says, Set, Aught To, Nein, Ten.

>>12525523
>tfw you will never patrol the clock with a cute little cousin
Just kill me now.

This is trivial if you assume the existence of prime factorization. If k, n are coprime, then n doesn't divide any of the k,2k,...,(n-1)k since n|kl implies n|l. If 0<=a<=b<n with n|(b-a)k, then n|(b-a). But 0<=b-a<n, so b-a=0. This means that 0,k,2k,...,(n-1)k mod n are pairwise distinct, i.e they are just some rearrangement of 0,1,2,..,n-1 mod n. This shows one way.
Conversely, assume you can "reach" 1: uk=1 mod n, i.e uk+vn=1. Then k,n are coprime.

>>12528898
Existence of prime factorization is trivial, and it's not what you're using here. You're using uniqueness of prime factorization, which is much more involved to prove. And the proofs of uniqueness that I've seen all presuppose the result you're proving, meaning your argument is circular.