Number Theory Revise 3

Continuing from here.

Book Referred: David Burton, Elementary Number Theory

Also, thanks to Pranjal Bhaiya and Ritam bhaiya for taking lectures in NT in EGMO Camp and Sophie!

We state and prove LTE first.

$$v_p(x^n-y^n)=v_p(x-y)+v_p(n), n|x-y, n\not\mid x.$$

Walkthough: We use induction on $v_p(n).$ [ We show for $v_p(n)=0, v_p(n)=1$ and then use induction.

1. We show it for $v_p(n)=0.$ That is show $v_p(x^n-y^n)=v_p(x-y)$

To show this is true, $$v_p(\frac{x^n-y^n}{x-y})=v_p(x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1})=0.$$

As $x\equiv y\pmod p.$

So,  $$x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1}\equiv nx^{n-1}\pmod p. $$

And $p\not\mid nx^{n-1}$

2. We show it for $v_p(n)=1.$ That is show $v_p(x^n-y^n)=v_p(x-y)+1$

To show this is true, $$v_p(\frac{x^n-y^n}{x-y})=v_p(x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1})=1.$$

As $x\equiv y\pmod p\implies x=y+pk$

So,  $$x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1}\pmod {p^2} $$

$$\equiv (pk+y)^{n-1}+(pk+y)^{n-2}y+(pk+y)^{n-3}y^2+\dots+y^{n-1}\pmod {p^2}$$

$$\equiv (y^{n-1}+pk\cdot (n-1)y^{n-2})+(y^{n-1}+ypk\cdot (n-2)y^{n-3})+\dots+y^{n-1}\pmod {p^2}$$

$$\equiv n\cdot y^{n-1}+pky^{n-2}\frac{(n-1)(n)}{2} \pmod {p^2}$$

Since $(n,p^2)=p.$ Let $n'=n/p.$

$$\equiv n'\cdot y+k\frac{(n-1)(n)}{2} \pmod {p}$$

but $p\not \mid n'\cdot y+k\frac{(n-1)(n)}{2}$

3. Let's assume it's true for $v_p=0,1,\dots, j-1.$ Now, we will show it's true for $v_p(n)=j.$

Then let $n=p^j\cdot c.$

Then $$v_p(x^n-y^n)=v_p(x^{p^j\cdot c}-y^{p^j\cdot c})=v_p((x^{p})^{p^{j-1}\cdot c}-(y^{p})^{p^{j-1}\cdot c})$$

$$=v_p(x^p-y^p)+v_p(p^{j-1}\cdot c)=v_p(x-y)+1+j-1=v_p(x-y)+v_p(n)$$

Orders: 

The following thing is what I learned yesterday from Pranjal Bhaiya's class.

To prove primitive roots exits modulo a prime.

Lemma: If $a$ has order $u$ and $b$ has order $v$ then there exist a number whose order is $LCM(u,v).$

Proof: Let $u_1|u, v_1|v, \gcd(u_1,v_1)=1, lcm(u_1,v_1)=uv.$

Then $a^{\frac{u}{u_1}}b^{\frac{v}{v_1}}$ has order $lcm(u,v).$

We also know that order would always divide $p-1.$

Now, take $g$ with maximal order $k.$

If $a$ has order $u.$ There exists a number whose order is $lcm(k,u).$

So for all $a\in \{1,\dots,p-1\}$ $o_p(a)|k\implies p|a^{k-1}-1$

But note that $x^k-1$ has $p-1$ roots.

So $k=p-1.$

Problem1:  If $p$ is a prime, then there  are exactly $\phi(p-1)$ incongruent primitive roots of $p.$

Proof: We know that $\{g,g^2,\dots,g^{p-1}\}\equiv \{1,2,3\dots, p-1\}.$

Now, if $g$ is a generator, then $g^a$ is too with $\gcd(a,p-1)=1.$

Problem2: For $k\ge 3,$ the integer $2^k$ has no primitive roots.

Proof: This is  because $2^{k-2}\equiv 1\mod 2^k.$

An integer $n>1$ has a primitve root if and only if $n=2,4,p^k,2p^k.$

Definition: $$(a/p)= 1 \text{ if } a \text{ is a QR } -1 \text{ else}.$$

Following are $7$ properties:

• If $a\equiv b\pmod p$ then $(a/p)=(b/p)$
• $(a^2/p)=1$
• $(a/p)=a^{p-1/2} \pmod p$
• $(ab/p)=(a/p)(b/p)$
• $(1/p)=1$
• $(-1/p)=(-1)^{\frac{p-1}{2}}$
• $(ab^2/p)=(a/p)$

The following theorem looked pretty interesting! 

Theorem: If $p$ is an odd prime, then $$\sum_{a=1}^{p-1}(a/p)=0$$

Proof:  $$\sum_{a=1}^{p-1}(a/p)=\sum_{a=1}^{\frac{p-1}{2}}$$

We let $g$ be the primitive root. Then $$\sum_{a=1}^{p-1}(a/p)=\sum (r^k/p)=\sum  (r^k)^{\frac{p-1}{2}}=\sum (-1)^k=0$$

Then, we have the famous Guass lemma! 

Theorem: Let $p$ be an odd prime and let $(a,p)=1.$ If $n$ denotes the number  of integers in the set $$S=\{a,2a,\dots, (p-1)/2\cdot a\}$$

whose remainders upon division by $p$ exceed $p/2,$ then $(a/p)=(-1)^n$

Proof: Let $r_1,r_2,\dots, r_m$ be the remainders not exceeding $p/2$ and $s_1,s_2,\dots, s_n$ exceed $p/2.$

Then note that $$\{r_1,r_2,\dots, r_m, p-s_1,p-s_2,\dots,p- s_n\}=\{1,\dots, \frac{p-1}{2}\}$$

Then, $$(\frac{p-1}{2})!=r_1\cdot r_2\dots r_m(p-s_1)(p-s_2)\dots, (p-s_n)=(-1)^n r_1\dots r_ms_1\cdots s_n$$

$$\equiv a^{p-1/2}(\frac{p-1}{2})!\pmod p$$

$$\implies (-1)^n\equiv a^{p-1/2}\pmod p$$

I would like to end with another theorem!

$$(p/q)(q/p)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$

Yess!! This basically ends this series! I might compile them in an overleaf file!

Thanks for reading!

Sunaina💜