NTIC The Conductor, solved

Section 9.7 The Conductor, solved

Do you remember A First Problem from the prologue? Somewhat surprisingly, perhaps, the same train of ideas from the proof that

ϕ

is multiplicative (Fact 9.5.2) can lead us finally to a nice proof of a formula for the conductor of any pair of relatively prime integers

m, n .

And this will be a concrete formula and proof we can actually understand!

🔗

Example 9.7.1.

As before, let us take a concrete example, for $m = 3, n = 5 .$ The first row indicates that each column is in one of the three equivalence classes modulo $3 .$ The ones which can be written $m x + n y$ are underlined.

$[0]$	$[1]$	$[2]$
$\underset{―}{0}$	$1$	$2$
$\underset{―}{3}$	$4$	$\underset{―}{5}$
$\underset{―}{6}$	$7$	$\underset{―}{8}$
$\underset{―}{9}$	$\underset{―}{10}$	$\underset{―}{11}$
$\underset{―}{12}$	$\underset{―}{13}$	$\underset{―}{14}$

Figure 9.7.2. Example of conductor analysis

In each column, look at the lowest number that can be represented. Do all of these have something in common? You may also want to see any commonalities in the numbers which cannot be represented.

To complement the table, try the following interact if you are online. This time elements that do have a representation as $m x + n y$ for nonnegative $x, y$ are indicated with exclamation points, by analogy with Example 9.5.3.

xxxxxxxxxx
 
@interact
def _(m=(3,[2..10]),n=(5,[2..10])):
    them = set([m*x+n*y for x in srange(n) for y in srange(m)])
    T = [['<m>[%s]</m>'%i for i in [0..m-1]]]
    for k in range(n):
        t = []
        for i in [0+k*m..m-1+k*m]:
            if i in them:
                t.append('%s !'%i)
            else:
                t.append('<m>%s</m>'%i)
        T.append(t)
    pretty_print(html(table(T, header_row=True, frame=True)))

🔗

In each column – that is to say, in each residue class modulo

m

– the lowest number that can be represented is a multiple of the other number

n .

We can justify this. If

m x + n y

is representable, then since

x, y \geq 0

we can just subtract off multiples of

m

until the number is just a multiple of

n,

which is obviously representable.

🔗

Now let's consider those multiples of

n,

but regarded modulo

m

(so, in different columns). Those must all land in different residue classes modulo

m,

presumably not in the same order as the usual order:

{[0], [n], [2 n], [3 n], \dots, [(m - 2) n], [(m - 1) n]} = {[0], [1], \dots, [m - 1]};

🔗

in the example above it was

{[0], [5], [10]} = {[0]_{3}, [2]_{3}, [1]_{3}} .

🔗

To see this⁴, consider that if

k n \equiv k^{'} n (mod m)

🔗

then we can just cancel

n

since

gcd (m, n) = 1,

and so

k \equiv k^{'} (mod m) .

🔗

Significantly, all numbers in each residue class (modulo

m

) greater than

k n

are also representable, since they are by definition a multiple of

m

greater than

k n;

since all residue classes are represented, this means there is a greatest number beyond which all are representable (the conductor).

Showing this fact was actually part of our proof of Fermat's Little Theorem, done in Exercise 7.7.10, but for completeness we include it now.

🔗

So what is the conductor? All these multiples of

n

are representable, so the largest numbers which are not representable in each class modulo

m

must be

k n - m .

The biggest of those is clearly the one with the biggest

k,

which is

(m - 1) n,

(m - 1) n - m

🔗

is the biggest number that can't be represented.

🔗

Alternately, we can write

(m - 1) n - m + 1 = m n - n - m + 1 = (m - 1) (n - 1)

🔗

for the smallest number above which all are represented, and we have a formula for the conductor.

🔗

We can summarize the entire discussion above as a proof of the first half of a solution⁵ to Exercise 1.4.7.

See [E.2.1, Exercise 1.25, solution] for an argument based on the geometric ideas we explored in Section 3.3.

🔗

Fact 9.7.3.

Given $m, n$ positive coprime integers, the conductor exists and is $(m - 1) (n - 1) .$ Exactly half the integers less than the conductor cannot be represented (and so half of them can be).

🔗

Proof.

See above for the formula for the conductor. Then we want to show that exactly half of the numbers below the conductor, including the (obviously) representable 0, are in fact representable. We will do this by pairing up the numbers from $0$ to $(m-1)n-m$ in a way such that each pair adds up to $(m-1)n-m\text{.}$ One of each pair will be representable, yielding the conclusion. (That the numbers arrange in pairs follows from noting that since $\gcd(m,n)=1\text{,}$ at least one of $m,n$ is odd, so there are an even number of integers from $0$ to $(m-1)n-m\text{.}$)

Suppose that $0\leq z\leq (m-1)n-m$ is representable, so that

\begin{equation*} z=mx+ny\; , m,n>0\text{.} \end{equation*}

Then consider the ‘complement’

\begin{equation*} z'=(m-1)n-m-z=m(-1-x)+n(m-1-y)\text{.} \end{equation*}

(In Example 9.7.1 we could consider $z=5$ and $z'=2\text{,}$ where $x=0,y=1\text{.}$)

We can bound the difference between $m$ and $y\text{,}$ or to be more precise $m-1$ and $y\text{.}$ If $m-1\leq y\text{,}$ then by construction $z\geq n(m-1)\text{,}$ but we are assuming $z$ is less than the conductor. So

\begin{equation*} m-1\geq m-1-y\geq 0\text{.} \end{equation*}

Certainly $(-1-x)<0\text{,}$ so it sure looks like $z'=m(-1-x)+n(m-1-y)$ is not representable.

Of course, it's possible that $z'$ could be written in a representable way by adding $m$s and subtracting $n$s. However, because $m$ and $n$ are coprime (think back to our methods in Section 3.1), the minimum possible number of each of these needed to do this would be $n$ added $m$s, and $m$ subtracted $n$s. Then we could write

\begin{equation*} z'=m(n-1-x)+n(-1-y)\text{,} \end{equation*}

but this has the problem now that $-1-y\lt 0\text{.}$

Finally, we can invert this argument to ensure this is a one-to-one correspondence between representable numbers and the rest. By Definition 2.4.1, any positive number $z'$ which is not representable must still have a representation as $mx+ny\text{,}$ just that either $x$ or $y$ (but not both) positive. Pick the representation $z'=mx+ny$ with the smallest positive $x$ (which exists by Axiom 1.2.1). Then by the argument in the previous paragraph, we know $z'$ can also be written as $m(x-n)+n(y+m)$ where now $x-n<0\text{,}$ since $x$ was the smallest positive option for the coefficient of $m\text{.}$ Since $z'$ isn't representable, then $y+m>0\text{.}$

We can rewrite this as $0<-y<m$ and $0<x<n\text{.}$ Then the ‘complement’ can be represented as follows, where in the last line we add $mn$ to the first term and subtract it from the second term:

\begin{align*} z \amp = (m-1)n-m-z' = (m-1)n-m-[mx+ny]\\ \amp =m(-1-x)+n(m-1-y)\\ \amp =m(-1-x)+mn+n(m-1-y)-mn\\ \amp =m(n-1-x)+n(-1-y)\text{.} \end{align*}

Since $x-n<0\text{,}$ we know $n>x$ which means $n-x-1\geq 0\text{;}$ since similarly $-y>0$ we know that $-1-y\geq 0\text{,}$ so $z$ really is representable, and we have completed the proof.