![\"drawing\"](\"./images/aims-za-logo.jpeg\"){kind=logo}
\n",
"| \n", " | Frobenius Number | \n", "Conductor | \n", "# Not Writable | \n", "
|---|---|---|---|
| \n", " | \n", " | \n", " | |
| \n", " | \n", " | \n", " | |
| \n", " | \n", " | None | \n", "|
| \n", " | \n", " | \n", " | |
| \n", " | \n", " | \n", " | |
| \n", " | \n", " | \n", " |
Let us work out by counting the numbers that are not writable. Let's start with $a=2$, $b=3$ and $a=3$, $b=4$.
" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recall that we discussed a few facts about integers earlier.
\n", "Fact: If $a$, $b>0$ are integers then we can write $a=qb+r$ with $0\\leq r Fact: In this situation, $\\gcd(a,b)=\\gcd(b,r)$. Here is another useful fact for our situation. Many of you already know this. Fact: For a given $n\\in \\mathbb{Z}$, the equation $ax+by=n$ has a solution in integers if and only if $\\gcd(a,b) \\mid n$. That is, you can't even write $ax+by=n$ if the greatest common divisor of $a$ and $b$ doesn't divide $n$. This was studied by the Greeks, known by Aryabhata in the Indian Middle Ages, and rediscovered by Bachet de Méziriac about 1600. Implication For Us: If $a$ and $b$ have a common divisor bigger than 1, there cannot be a conductor. We already saw an example in class. I want you to think about why this might be. I can prove the facts above. But just proving things are true and using them isn't enough. Why is it true, intuitively? I believe the right place to do this is in geometry. (The little gray dots in the graph above are called the integer lattice. You may treat this as a definition. There are many lattices, but only one which is basically all the intersections of $y=m,x=n$ for all integers $m,n$. So for instance $(-2,3)$ is probably visible; however, note that $(-1,1/2)$ is not a little dot, because it doesn't have integer values.) Since $ax+by=c$ may be thought of as a line (in fact, the line $$y=-\\frac{a}{b}x+\\frac{c}{b}$$ with slope $-\\frac{a}{b}$), we now have a completely different interpretation of this very basic number theory question (the \"linear Diophantine equation\"). It is simply asking, \"When (for what $a$, $b$, $c$ combinations) does the line hit this lattice? If it does, can you tell me all intersections?\" If you play around with the sliders you will quickly see that things work out just as promised in the theorems. Now let's connect this to some of the conductor questions. Given positive integers $a$ and $b$: Let's explore this - even in cases where the conductor is not very interesting. How many such points are there in the following cases? Again, you should be able to start exploring and experimenting. Naturally, in this case I don't only expect you to use my graphic, which is a big challenge for you to program right now. Try instead to write your own program to explore this question.Rethinking the Problem
\n",
"\n",
"
\n",
"\n",
"
\n",
"\n",
"
\n",
"\n",
"
\n",
"