#Bezout's Identity

[isomorphismes]

What is an algebraic variety?

The shape of the answers to equations.

Start with an equation like

Please take notice of three things:

the "+1" is used to shift the "zero line" or "answer line" up and down. So in fact "zero" is arbitrary.

This specific equation's left-hand side (which does not correspond to the picture; the picture is just supposed to be "an arbitrary continuous function") factors into

which factors into

I didn't specify what "x" is--it could belong to any coherent corpus of generalised "numbers" where "multiplicative identity" ("one") is meaningful

could be matrices, functional space, something I haven't thought of yet

tropical geometry. redefine "times" as ^ and "plus" as v

set theory union intersection

it is just a shorthand for

calculus 101. polynomials.

so not the price train of a narrowly-held company (all jumps)

fundamental theorem of algebra: Copf; is closed

as a mapping to zeroes

letting the LHS handle all the info (instead of x^2=16) is better organisation

affine -- geometric -- "forget the origin"

affine variety

kernel -- what's thrown in the trash. linear algebra.

intersections. system of equations. pretend a physical system. like going to the moon. 

intersection. it has to solve all of them.

bezout's theorem.

the body

[mathematicianadda]

Choosing a Discrete Mathematics Topic to Explain

Instead of a final exam, my teacher decided to assign us homework where we choose a theorem or a concept that we've covered in class and explain it. We then prepare an exercise about our topic and solve the exercise.

I LOVE this homework, as it gives me so much freedom. Also, since it replaces the final exam, I think I am allowed to go more in-depth on a topic, rather than the usual 1-2 page assignments.

However, I don't know what to pick because I want my topic and exercise to be something interesting and I am a little picky. Do you guys have any suggestions for a topic and an interesting exercise? I am not asking you to solve the exercise for me. I would like to work on it on my own. My only request is that it is not something that is done to death i.e. that is given as an exercise in every Discrete Mathematics class. By the way, this is my first year as a maths undergraduate, so please go easy on me.

What we've covered in class: Number Theory (Modular Arithmetic, Fermat's Little Theorem, Bezout's Identity, Chinese Remainder Theorem, Fundamental Theorem of Arithmetic, etc.), Induction and Recursion, Counting (Pigeonhole Principle, The Binomial Theorem, etc.), Discrete Probability (Bayes' Theorem, Expected Value and Variance), Advanced Counting Techniques (Solving Linear Recurrence Relations, Generating Functions, Inclusion-Exclusion Principle), Graphs (Euler and Hamilton Paths, Planar Graphs, Graph Coloring), Trees.

submitted by /u/dnzszr [link] [comments] from math https://ift.tt/2Yk8c3F https://ift.tt/eA8V8J from Blogger https://ift.tt/3fMcW87

[learning2program]

Interesting fact about the GCD

Today, we will be utilizing the Euclidean algorithm module we wrote earlier to study an interesting fact about GCD.

I learned a cool new fact today that I thought I’d share. It uses the Euclidean algorithm module that I wrote up earlier like I said, so if you haven’t see that yet you should read it here.

Today we will be studying the fact that

\[\sum_{\substack{1 \leq a \leq n\ gcd(a, n) =1}} a = \frac{n \phi(n)}{2}. \]

I’ll first cover some preliminaries though. First, one should know what I mean when I say

\[ \phi(n). \]

This is known as the Euler totient function, and is an interesting function in number theory. It counts the number of numbers coprime to your input which are less than your value. It has a variety of applications and a long history behind it which is outside the scope of this post, but you can see more here.

Next, we’ll need a theorem.

Theorem: If gcd(a, n) = 1, then gcd(n-a, n) = 1.

Proof:

By Bezout's Identity, we have that gcd(a, n) = 1 implies

\[ \alpha a + \beta n = 1.\]

Add and subtract alpha n to the left hand side to get

\[ \alpha a + \beta n - \alpha n + \alpha n = 1.\] By simple algebra, we get

\[ \alpha(a - n) + n(\beta + \alpha) = 1.\]

Let

\[ \gamma = \beta + \alpha\]

for notational simplicity. Then we have that

\[ \alpha(a-n) + n\gamma = 1.\]

By the converse of Bezout's Identity, this then gives us

\[\gcd(a-n, n) = 1.\]

However, note that

\[\gcd(-(a-n),n) = \gcd(a-n, n)\]

(this follows since if d | m, n then d | -m, n; so we have that (-m,n) and (m,n) have the same set of common divisors, which implies the same gcd), which then implies gcd(n-a, n) = 1. Q.E.D.

Using these two, the construction of the earlier claim is rather clear. We can use an argument similar to that of Gauss when counting the integers. Let

\[x_1, \ldots, x_{\phi(n)} \]

be the integers which are coprime to n in ascending order. Then we can arrange the integers to then be

\[ x_1, \ldots, x_{\phi(n)} \]

\[ x_{\phi(n)}, \ldots, x_1. \]

Add the integers vertically to then get $\phi(n)$ instances of n. This is clear from the theorem earlier. We however have added the sequence to itself, and so dividing it by two then gives us the sum of the coprime integers. Therefore, we have

\[\sum_{1 \leq a \leq n, gcd(a, n) =1} a = \frac{n \phi(n)}{2}. \]

One can then check this for the first however many integers using python. For simplicity, I will be only checking the first 30 integers; however, you can modify the file to be as large as you want (it will probably start slowing down a lot as you set the integer amount to be higher and higher, however). There is really only one function that we will be doing to use this, though we will import the gcd function from our euclideanalg module.

check(p): The function starts by constructing a list of all of the positive integers less than p which are coprime to p. Here, we use the gcd function to check if gcd(i, p) == 1 at each iteration of i. Next, we sum up each of the numbers in this new list that we’ve constructed and save it in a variable denoted sum. We take the length of the list (which is equivalent to the Euler totient of p) and then calculate the value

\[\frac{n \phi(n)}{2}. \]

If the sum of the coprimes and this value are equivalent, the function returns true; otherwise, the function returns false (however, by the prior claims, we have shown that this should never return false). We now have a tangible way to view whether or not this claim is true! The code for the function follows

def check(p): print('checking ' + str(p)) primes = [] for i in range(1, p): if gcd(p, i) == 1: primes.append(i) sum = 0 print('coprimes: ' + str(primes)) for i in primes: sum += i print('sum of coprimes: ' + str(sum)) #now to actually check tot = len(primes) print('euler totient function: ' + str(tot)) total = (p * tot)/2 if total == sum: return True else: return False

As always, you can find this on the github page here.

[gonnaflunkscience-blog]

Bezout's Identity

Bezout's Identity, The Impossibility of Silence

Bezout's Identity was Anton and Al, two musicians formerly of The Summer We Went West and Dawn Treader and currently parts of Monument (Anton) and Shat Shorts (Anton and Al.)

They were a two-piece emo band from College Park, Maryland that I experienced entirely through the internet, at an age where I spent hours on myspace listening to handfuls of tracks by bands I should have been seeing in basements. (I'm thinking 2007, a year I will come back to again and again and never leave unless I'm writing about a Japanese band.) 

twinkly guitar, or noodly, as I recall it then. Overt vocal melodies that aren't pandering to sing-alongs. Interesting song compositions. There's some clinical analysis to ignore. Bezout's have something that gets under my skin, maybe you'll feel it.

I have four of their songs, nabbed from myspace. I only know the origin of one of these tunes - The Impossibility of Silence - which is credited to a split with Peter and Craig. Knowing this, I cornered Peter of the aforementioned duo in a kitchen in Lancaster once and inquired about Bezout's. He claimed to recall at least five songs. Hoping to track down that last one someday.

Here's four tunes, two with percussion, two with less of that, all four really excellent. Listen to 'The Impossibility of Silence' up there,  the song that came into my head years after first hearing it and made me dig through decaying social media sites to hear it once more (and again, and again, and again.)

Would you like some tea?

-d (thanks for letting me post, matt.)