## Math Genius: Prime decomposition of pR in \$mathbb{A}cap mathbb{Q}[alpha]\$ for \$alpha={^3sqrt{hk^2}}\$ if p is a prime such that \$p^2|m\$

I’m going through Marcus number Field chapter 3 an I’m finding very hard to understand the part about the decomposition of pR (theorem 27) that tells us that if $$pnot||R/Z[alpha ]|$$ then we can decompose $$pR$$ by looking at a factorization of it’s minimal polynomial (Kummer’s theorem?)

In partcular I’m stuck on exercise 26

Let $$alpha={ ^{3}sqrt{m}}$$ where m is a cubefree integer, $$K = mathbb{Q}[alpha]$$, $$R = mathbb{A} cap mathbb{Q}[alpha]$$

1. Show that if p is a prime $$neq 3$$ and $$p^2 not|m$$ , then the prime decomposition of pR
can be determined by factoring $$x^3 − m; mod; p.$$ (See Theorem 27 and exercise
41, chapter 2 (this tells us the discriminat and the integral bases I write below).)

2. Suppose $$p^2 | m$$. Writing $$m = hk^2$$ as in exercise 41, chapter 2, set $$gamma= frac{alpha^2}{k}.$$
Show that p does not divide $$|R/Z[gamma ]|$$; use this to determine the prime decomposition
of pR.

3. Determine the prime decomposition of 3R when $$mnotequiv pm 1$$ (mod 9).

4. Determine the prime decomposition of 3R when m = 10. (Hint: Set $$beta = (alpha − 1)^2/3$$ and use exercise 18 to show that disc(β) = 4 disc(R). Also note exercise
41(d), chapter 2 (this tells us that $$beta^3-beta^2+left(frac{ 1+2m}{3}right)beta-frac{(m-1)^2}{27}=0))$$ Show that this always works for $$mequiv pm 1; (mod; 9)$$ except
possibly when $$mequiv pm 8; (mod; 27)$$.
5. Show that 9 $$not|$$ disc(R) when $$mequiv pm 1; (mod; 9)$$; use this to show that 3R is not
the cube of a prime ideal. Assuming the converse of Theorem
24, show that 3R = $$P^2Q$$ where P and Q are distinct primes of R.

I think I’ve done point 1) using the fact that $$p^2not| disc(alpha)$$ implies we can use theorem 27 that tells us exactly that we can decompose pR simply by factorizing the minimal polynomial of $$alpha$$, but the problem is now point 2) (and the ones after since they rely on 2).

I was able to prove that $$gamma=sqrt{h^2k}$$ and that $$p^2not| h^2k$$ so either we can use the fact above or $$p^2|disc(alpha)=-27^2*k^2hRightarrow p^2|27^2$$ so p=3, but now I don’t know how to prove that 3 doesn’t divide $$|R/mathbb{Z}[alpha]|$$ since for me the latter is always divisible by 3.

An integral base of the above is either
$$left(1,alpha,frac{alpha^2+k^2alpha+k^2}{3k}right),quad left(1,alpha,frac{alpha^2-k^2alpha+k^2}{3k}right),quad left(1,alpha,frac{alpha^2}{k}right)$$
if respectivly $$mequiv 1; (mod; 9)$$, $$mequiv -1; (mod; 9)$$, $$mnotequiv pm1; (mod; 9)$$

Any help would be welcomed, even more if quite specific on the calculations since I think there is something I miss on a theoretical level.

Exercise 18 Let K be a number field of degree n over $$mathbb{Q}$$ , and let $$alpha_1, dots , alpha_n in K.$$

1. Show that $$disc(ralpha_1, alpha_2, dots , alpha_n) = r^2 disc(alpha_1, dots , alpha_n)$$ for all r $$in mathbb{Q}$$.

2. Let $$beta$$ be a linear combination of $$alpha_2, dots , alpha_n$$ with coefficients in $$mathbb{Q}$$. Show that
$$disc(alpha_1 + beta, alpha_2, dots , alpha_n) = disc(alpha_1, dots , alpha_n).$$

Theorem 24 Let p be a prime in $$mathbb{Z}$$, and suppose p is ramified in a number ring R.
Then p | disc(R).

UPDATE: The question is still without answer so for now I’ll post my solution to the first two points, then if a better one comes I’ll be happy to set it as solving the question.

1. Uniforming the notation between this exercise and therem 27 of Marcus we have
$$L=mathbb{Q}[alpha]quad S=mathbb{A}cap mathbb{Q}[alpha]quad K=mathbb{Q}quad R=mathbb{Z}$$ so to use theorem 27 we have to check
$$pnot|left|frac{mathbb{A}cap mathbb{Q}[alpha]}{mathbb{Z}[alpha]}right|$$ but actually first we can use the corollary telling us that the hypotesis are satisfied if $$p^2not|disc(alpha)$$,
exercise 41 in chapter 2 tells us that in our case $$disc(alpha)=-27^2m$$ and so if $$pneq 3wedge p^2|m$$ we are in the hypotesis of the corollary and thus of the theorem and so we can decompose pR by factoring $$x^3-m$$;

2. In this case the hypotesis of the corollary are not satisfied. We have also that $$p^2|miff p^2|hvee p^2|k^2$$ but since h is squarefree we have that it has to be $$p^2|k^2iff p|kiff pnot|h$$ since they are coprime. Now we can write
$$alpha=sqrt{hk^2}iff alpha^2=sqrt{h^2k^4}iff gamma=frac{alpha^2}{k}=sqrt{h^2k}$$ and we have that $$p^2|h^2kiff p^2|h^2iff p|h$$ which is not true so $$p^2not| h^2k$$.
But now $$p|h^2k=n$$ but $$p^2not|h^2k$$ so $$x^3-n$$ is a p-Eisentstein polynomial and we can use the following theorem to deduce $$pnot| |mathbb{A}cap mathbb{Q}[gamma]/mathbb{Z}[gamma]|$$

Let K = $$mathbb{Q}(alpha)$$ where $$alphain mathbb{A}cap mathbb{Q}[alpha]$$ is the root of an Eisenstein polynomial at p,
with degree n. Then $$p not| |mathbb{A}cap mathbb{Q}[alpha] / mathbb{Z}[alpha]|$$.

## Math Genius: How to prove that no prime factor of \$x^2-x+1\$ is of the form \$6k-1\$

Consider sequence \$x^2-x+1\$ (\$1,3,7,13,21,31,43,57,73,91,dots\$). Let’s consider prime factorization of each term.
\$\$3=3\$\$
\$\$7=7\$\$
\$\$13=13\$\$
\$\$21=3times7\$\$

It seems that the only prime factors we ever get are 3 and those of the form \$6k+1\$. In fact, prime factorization of the first 10 000 terms of the sequence gives 7233 distinct primes and all of them (except 3) are \$6k+1\$.

That no member of the sequence is ever divisible by a prime of the form \$6k-1\$ is a purely empirical conjecture. Is there a formal proof for it (or a counterexample)?

Let \$p\$ be a prime.

\$\$pmid x^2-x+1\$\$

\$\$implies pmid 4left(x^2-x+1right)=(2x-1)^2+3\$\$

\$\$iff (2x-1)^2equiv -3pmod{p}\$\$

By Quadratic Reciprocity this implies either \$p=2\$ or \$p=3\$ or \$pequiv 1pmod{3}\$.

\$2\$ and \$3\$ are not of the form \$6k-1\$. And if \$pequiv 1pmod{3}\$, then \$p\$ is not of the form \$6k-1\$ because \$6k-1notequiv 1pmod{3}\$.

Assume that a prime \$p|n^2-n+1\$ form some integer \$n\$. Then we also have that
\$p\$ is a factor of \$(n+1)(n^2-n+1)=n^3+1\$. In other words
\$\$
\$\$
Let’s try to figure out the order of the residue class of \$n\$ modulo \$p\$.
From \$(*)\$ it follows that \$n^6equiv1pmod p\$, so the order is a factor of six, but not a factor of three.

We cannot have \$n^2equiv1pmod p\$, for then \$p\$ is also a factor of \$(n^2-1)-(n^2-n+1)=n-2\$. When \$nequiv 2pmod p\$, then \$n^2-n+1equiv3pmod p\$, so we must be in the exceptional case \$p=3\$. Otherwise the order is not a factor of two.

So if \$p>3\$ the order is six. But by Lagrange’s theorem from elementary group theory the order is a factor of \$p-1\$. QED

We may notice that
\$\$ q(x)=x^2-x+1 = Phi_6(x) = frac{(x^6-1)(x-1)}{(x^3-1)(x^2-1)}\$\$
is a cyclotomic polynomial. If for some prime \$p>6\$ we have \$q(x)equiv 0pmod{p}\$, that means that \$x\$ has order \$6\$ in \$mathbb{F}_p^*\$, since by the above identity the roots of \$q(x)\$ are exactly the primitive sixth roots of unity. By Lagrange’s theorem, the order of an element of \$mathbb{F}_{p}^*\$ has to be a divisor of the order of the group, that is \$p-1\$. So:
This argument is also the key for an elementary proof of the following fact: for every \$ngeq 2\$, there are infinite primes of the form \$kn+1\$. It is interesting to point out that nowadays an elementary proof of the more general Dirichlet’s theorem, avoiding the Selberg-Erdos machinery involved in the elementary proof of the PNT, is still missing.

As a complement to @user236182, let us show that \$(frac{-3}{p})=1\$ is a necessary and sufficient condition for an odd prime \$p\$ to divide \$x^2 – x + 1\$ (where \$x\$ is an integer). Just notice that \$x^2 – x + 1 = (x + j)(x + j^2)\$, where \$j\$ denotes a primitive cubic root of \$1\$. Since the ring \$mathbf Z [j]\$ is an UFD, the division condition above is equivalent to the splitting of \$p\$ in the quadratic field \$ mathbf Q (j) = mathbf Q (sqrt-3)\$, and this is known to be equivalent to \$(frac{-3}{p})=1\$ .

First, some facts about numbers in your sequence. Let $$n=x^2-x+1$$. If $$x=3k-1$$, then
begin{align*} n=x^2-x+1 &= (3k-1)^2-(3k-1)+1\ &= 9k^2-6k+1-3k+1+1\ &= 9k^2-9k+3\ implies n/3 &= 3k^2-3k+1 end{align*}
$$k^2$$ and $$k$$ have the same parity. Therefore
$$n/3=1mod 6$$. If $$x$$ is any other integer then $$n=1mod 6$$ as can be easily checked. Thus $$n$$ is odd; and, after a factor of 3 has been extracted, if there is one, the result is 1, modulo 6. In any case $$nne 5mod 6$$.

Suppose your conjecture is wrong, and let $$p$$ be the lowest prime counterexample, i.e. lowest prime $$pne3$$, not of the form $$6k+1$$, which divides a number that is in your sequence.

Let prime $$p$$ divide $$n=x^2-x+1$$. Then $$pne 2$$. Because $$pne3$$ and $$pne1mod 6$$, $$p=5mod 6$$.

Let $$x=sp+r$$ where $$s$$ is the nearest integer to $$x/p$$, so $$|r|. Then
begin{align*} n=x^2-x+1 &= (sp+r)^2-(sp+r)+1\ &= s^2p^2+2srp+r^2-sp-r+1\ &= Ap+r^2-r+1 end{align*}
where $$A=s^2p+2sr-s$$. Thus
$$pmid r^2-r+1$$, so, for some integer $$m’$$,
begin{align*} m’p &= r^2-r+1\ &leqslant r^2\ &

If $$3mid m’$$, let $$m=m’/3$$, otherwise let $$m=m’$$. Then $$3nmid m$$, and $$mleqslant m'.

Because $$m and $$p$$ is the smallest counterexample, each prime factor $$q$$ of $$m$$ is 1, modulo 6 (because $$qleqslant m so $$q$$ is not a counterexample). So, modulo 6, $$m=1$$, $$p=5$$, so $$mp=5$$. But $$mp = r^2-r+1$$ is in your sequence, so $$mpne 5mod 6$$. This is a contradiction. (In fact, for any integer $$m$$ where $$m=5mod 6$$, at least one prime factor of $$m$$ is $$q=5mod 6$$.)

## Math Genius: Finding prime factors of \$2^{300} – 1\$

My initial approach to this problem was to use Fermat’s Little Theorem:

We seek primes $$p$$ such that $$2^{300} equiv 1 pmod{p}$$.
By Fermat’s Little Theorem, if $$a^{p-1} = 2^{300}$$ for some prime $$p$$ and $$a in mathbb{Z}$$ such that $$p nmid a$$, then $$p$$ is a prime factor of $$2^{300} – 1$$.

Instinctively, I set $$a=2$$. Now, if $$p-1,|,300$$ and $$p nmid a$$, then $$p$$ is a factor. Using this method, I listed all the factors of 300, and found that the following primes divide $$2^{300} – 1$$:

p = 3, 5, 7, 11, 13, 31, 61, 101, 151.

However, when I checked for other primes using Wolfram Alpha, I found that $$p = 41$$ also a factor. Obviously, my method wouldn’t work since $$40 nmid 300$$. Is there some other method (besides guess and check) which would reveal these extra prime factors?

Yes. We know that
$$2^n-1 big| 2^m-1$$
whenever $$n|m$$. In particular, because $$20|300$$, $$2^{20}-1$$ divides $$2^{300}-1$$, and any prime that divides $$2^{20}-1$$ will thus also divide $$2^{300}-1$$.

Now, we have $$41$$ divides $$2^{20}-1$$. Can you show this?

$$2^{300} equiv 1 bmod{p}$$ implies $$2^{d} equiv 1 bmod{p}$$, where $$d=gcd(300,p-1)$$. So you have to consider also the primes $$p$$ such that $$p-1$$ has a common factor with $$300$$ (larger than $$2$$). Hence $$41$$ is a possibility.

Another method that gives you at least some factors is a cyclotomic factorization:
$$x^{n}-1=prod _{dmid n}Phi _{d}(x)$$
and so
$$x^{300}-1=(x – 1) (x + 1) (x^2 + 1) (x^2 – x + 1) (x^2 + x + 1) (x^4 – x^2 + 1) (x^4 – x^3 + x^2 – x + 1) (x^4 + x^3 + x^2 + x + 1) (x^8 – x^6 + x^4 – x^2 + 1) (x^8 – x^7 + x^5 – x^4 + x^3 – x + 1) (x^8 + x^7 – x^5 – x^4 – x^3 + x + 1) (x^{16} + x^{14} – x^{10} – x^8 – x^6 + x^2 + 1) (x^{20} – x^{15} + x^{10} – x^5 + 1) (x^{20} + x^{15} + x^{10} + x^5 + 1) (x^{40} – x^{30} + x^{20} – x^{10} + 1) (x^{40} – x^{35} + x^{25} – x^{20} + x^{15} – x^5 + 1) (x^{40} + x^{35} – x^{25} – x^{20} – x^{15} + x^5 + 1) (x^{80} + x^{70} – x^{50} – x^{40} – x^{30} + x^{10} + 1)$$
Setting $$x=2$$ gives
$$2^{300}-1=1 cdot 3 cdot 5 cdot 3 cdot 7 cdot 13 cdot 11 cdot 31 cdot 205 cdot 151 cdot 331 cdot 80581 cdot 1016801 cdot 1082401cdots$$
which already gives you several primes and smaller factors that are easy to factor.

$$2^{300}-1=3^2×5^3×7×11×13×31×41×61×101×151×251×331×601×1201×1321×1801×4051×8101×63901×100801×268501×10567201×13334701×1182468601×1133836730401$$
but its unlikely to be easy to get by hand.

## Math Genius: Euler’s product formula in number theory

Is there intuitive proof of Euler’s product formula in number theory (not searching for probabilistic proof) which is used to compute Euler’s totient function?

One intuition uses Inclusion-Exclusion. For example, if $$n$$ is divisible by three distinct primes $$p$$, $$q$$, and $$r$$, then

$$n-left({nover p}+{nover q}+{nover r}right)+left({nover pq}+{nover pr}+{nover qr} right)-{nover pqr}$$

counts all the numbers less than $$n$$ that are not divisible by $$p$$, $$q$$, or $$r$$, which is to say the numbers that are relatively prime to $$n$$. But we see that this is equal to the product

$$nleft(1-{1over p} right)left(1-{1over q} right)left(1-{1over r} right)$$

Intuitively $$frac1{1-p_i^{-s}} = 1+p_i^{-s} + left(p_i^{-s}right)^2 + cdots =left(p_i^0right)^{-s}+left(p_i^1right)^{-s} + left(p_i^2right)^{-s} + cdots$$

so

$$prodlimits_{i=1}^infty frac1{1-p_i^{-s}} \=left(left(2^0right)^{-s}+left(2^1right)^{-s} + left(2^2right)^{-s} + cdots right) times left(left(3^0right)^{-s}+left(3^1right)^{-s} + left(3^2right)^{-s} + cdots right) \ times left(left(5^0right)^{-s}+left(5^1right)^{-s} + left(5^2right)^{-s} + cdots right) times cdots \=left(2^0right)^{-s} left(3^0right)^{-s} left(5^0right)^{-s}cdots + left(2^1right)^{-s} left(3^0right)^{-s} left(5^0right)^{-s}cdots + left(2^0right)^{-s} left(3^1right)^{-s} left(5^0right)^{-s}cdots \ + left(2^2right)^{-s} left(3^0right)^{-s} left(5^0right)^{-s}cdots + left(2^0right)^{-s} left(3^0right)^{-s} left(5^1right)^{-s}cdots + cdots \ = left(2^0 3^0 5^0right)^{-s} +left(2^1 3^0 5^0right)^{-s} +left(2^0 3^1 5^0right)^{-s} +left(2^2 3^0 5^0right)^{-s} +left(2^0 3^0 5^1right)^{-s} +cdots \ = 1^{-s} + 2^{-s} + 3^{-s} +4^{-s} +5^{-s} + cdots \ = sumlimits_{n=1}^infty frac{1}{n^s}$$

though for a proof you will want to use convergence and the fundamental theorem of arithmetic

Presumably you mean $$phi(n)=nprod_{p|n}(1-1/p)$$. Well, I think the best intuition is to understand it.

First, let’s look at $$phi(p^n)$$. It’s easy to see that you can multiply $$p$$ with any number less than $$p^{n-1}$$, to get precisely all the numbers less than $$p^n$$ not relatively prime to $$p^n$$. Thus we get $$phi(p^n)=p^n-p^{n-1}=p^n(1-1/p)$$.

From here all we need is the content of a very famous theorem, called the Chinese Remainder Theorem. It implies that the totient function is multiplicative. That is, when $$(m,n)=1$$, we have $$phi(mn)=phi(m)phi(n)$$. As to CRT, it is not that difficult given Bezout’s identity.

From these two facts the result follows.

## Math Genius: Finding all no-congruent primitive roots \$pmod{29}\$

Finding all no-congruent primitive roots $$pmod{29}$$.

I have found that $$2$$ is a primitve root $$pmod{29}$$
Then I found that is it 12 no-congruent roots, since $$varphi(varphi(29)) = 12$$
Then I found that:

$$r_1=2^1=2bmod (29)\r_2=2^3=8bmod (29)\r_3=2^5=3bmod (29)\r_4=2^{11}=18bmod (29)\r_ 5=2^{13}=18bmod (29)\r_6=2^{17}=21bmod (29)\r_7=2^{19}=21bmod (29)\r_8=2^{23}=10bmod (29)\r_9=2^{27}=15bmod (29)\r_{10}=2^{29}=2bmod (29)$$

Is $$10$$ of these roots $$12$$ roots. Took the power of the primes from $$1-29$$ (not the primefactors of $$varphi, 2$$ and $$7$$), but I am missing $$2$$ roots, and I don’t understand how to find them. I have used all prime powers.

You should use all powers of $$2$$ that are relatively prime to $$28$$.

The two roots you are missing are $$2^9$$ and $$2^{15}.$$

$$9$$ and $$15$$ are not prime (they are multiples of $$3$$), but they share no factors with $$28$$.

(I also note that you have wrong values for $$2^{13}$$ and $$2^{19}bmod29$$;

they aren’t the same as $$2^{11}$$ and $$2^{17}$$, respectively.)

Also, you are missing $$2^{25}$$; you have $$2^{29}$$, which is the same as $$2^{1}bmod28$$, instead.

Like my answer here Order of elements modulo p,

We can say $$2^r$$ is a primitive root of $$29$$
iff $$(r,phi(29))=1$$

Now $$phi(phi(29))=phi(7)cdotphi(4)=?$$

## Math Genius: Finding all no-congruent primitive roots \$pmod{29}\$

Finding all no-congruent primitive roots $$pmod{29}$$.

I have found that $$2$$ is a primitve root $$pmod{29}$$
Then I found that is it 12 no-congruent roots, since $$varphi(varphi(29)) = 12$$
Then I found that:

$$r_1=2^1=2bmod (29)\r_2=2^3=8bmod (29)\r_3=2^5=3bmod (29)\r_4=2^{11}=18bmod (29)\r_ 5=2^{13}=18bmod (29)\r_6=2^{17}=21bmod (29)\r_7=2^{19}=21bmod (29)\r_8=2^{23}=10bmod (29)\r_9=2^{27}=15bmod (29)\r_{10}=2^{29}=2bmod (29)$$

Is $$10$$ of these roots $$12$$ roots. Took the power of the primes from $$1-29$$ (not the primefactors of $$varphi, 2$$ and $$7$$), but I am missing $$2$$ roots, and I don’t understand how to find them. I have used all prime powers.

You should use all powers of $$2$$ that are relatively prime to $$28$$.

The two roots you are missing are $$2^9$$ and $$2^{15}.$$

$$9$$ and $$15$$ are not prime (they are multiples of $$3$$), but they share no factors with $$28$$.

(I also note that you have wrong values for $$2^{13}$$ and $$2^{19}bmod29$$;

they aren’t the same as $$2^{11}$$ and $$2^{17}$$, respectively.)

Also, you are missing $$2^{25}$$; you have $$2^{29}$$, which is the same as $$2^{1}bmod28$$, instead.

Like my answer here Order of elements modulo p,

We can say $$2^r$$ is a primitive root of $$29$$
iff $$(r,phi(29))=1$$

Now $$phi(phi(29))=phi(7)cdotphi(4)=?$$

## Math Genius: Prime decomposition of pR in \$mathbb{A}cap mathbb{Q}[alpha]\$ for \$alpha={^3sqrt{hk^2}}\$ if p is a prime such that \$p^2|m\$

I’m going through Marcus number Field chapter 3 an I’m finding very hard to understand the part about the decomposition of pR (theorem 27) that tells us that if $$pnot||R/Z[alpha ]|$$ then we can decompose $$pR$$ by looking at a factorization of it’s minimal polynomial (Kummer’s theorem?)

In partcular I’m stuck on exercise 26

Let $$alpha={ ^{3}sqrt{m}}$$ where m is a cubefree integer, $$K = mathbb{Q}[alpha]$$, $$R = mathbb{A} cap mathbb{Q}[alpha]$$

1. Show that if p is a prime $$neq 3$$ and $$p^2 not|m$$ , then the prime decomposition of pR
can be determined by factoring $$x^3 − m; mod; p.$$ (See Theorem 27 and exercise
41, chapter 2 (this tells us the discriminat and the integral bases I write below).)

2. Suppose $$p^2 | m$$. Writing $$m = hk^2$$ as in exercise 41, chapter 2, set $$gamma= frac{alpha^2}{k}.$$
Show that p does not divide $$|R/Z[gamma ]|$$; use this to determine the prime decomposition
of pR.

3. Determine the prime decomposition of 3R when $$mnotequiv pm 1$$ (mod 9).

4. Determine the prime decomposition of 3R when m = 10. (Hint: Set $$beta = (alpha − 1)^2/3$$ and use exercise 18 to show that disc(β) = 4 disc(R). Also note exercise
41(d), chapter 2 (this tells us that $$beta^3-beta^2+left(frac{ 1+2m}{3}right)beta-frac{(m-1)^2}{27}=0))$$ Show that this always works for $$mequiv pm 1; (mod; 9)$$ except
possibly when $$mequiv pm 8; (mod; 27)$$.
5. Show that 9 $$not|$$ disc(R) when $$mequiv pm 1; (mod; 9)$$; use this to show that 3R is not
the cube of a prime ideal. Assuming the converse of Theorem
24, show that 3R = $$P^2Q$$ where P and Q are distinct primes of R.

I think I’ve done point 1) using the fact that $$p^2not| disc(alpha)$$ implies we can use theorem 27 that tells us exactly that we can decompose pR simply by factorizing the minimal polynomial of $$alpha$$, but the problem is now point 2) (and the ones after since they rely on 2).

I was able to prove that $$gamma=sqrt{h^2k}$$ and that $$p^2not| h^2k$$ so either we can use the fact above or $$p^2|disc(alpha)=-27^2*k^2hRightarrow p^2|27^2$$ so p=3, but now I don’t know how to prove that 3 doesn’t divide $$|R/mathbb{Z}[alpha]|$$ since for me the latter is always divisible by 3.

An integral base of the above is either
$$left(1,alpha,frac{alpha^2+k^2alpha+k^2}{3k}right),quad left(1,alpha,frac{alpha^2-k^2alpha+k^2}{3k}right),quad left(1,alpha,frac{alpha^2}{k}right)$$
if respectivly $$mequiv 1; (mod; 9)$$, $$mequiv -1; (mod; 9)$$, $$mnotequiv pm1; (mod; 9)$$

Any help would be welcomed, even more if quite specific on the calculations since I think there is something I miss on a theoretical level.

Exercise 18 Let K be a number field of degree n over $$mathbb{Q}$$ , and let $$alpha_1, dots , alpha_n in K.$$

1. Show that $$disc(ralpha_1, alpha_2, dots , alpha_n) = r^2 disc(alpha_1, dots , alpha_n)$$ for all r $$in mathbb{Q}$$.

2. Let $$beta$$ be a linear combination of $$alpha_2, dots , alpha_n$$ with coefficients in $$mathbb{Q}$$. Show that
$$disc(alpha_1 + beta, alpha_2, dots , alpha_n) = disc(alpha_1, dots , alpha_n).$$

Theorem 24 Let p be a prime in $$mathbb{Z}$$, and suppose p is ramified in a number ring R.
Then p | disc(R).

UPDATE: The question is still without answer so for now I’ll post my solution to the first two points, then if a better one comes I’ll be happy to set it as solving the question.

1. Uniforming the notation between this exercise and therem 27 of Marcus we have
$$L=mathbb{Q}[alpha]quad S=mathbb{A}cap mathbb{Q}[alpha]quad K=mathbb{Q}quad R=mathbb{Z}$$ so to use theorem 27 we have to check
$$pnot|left|frac{mathbb{A}cap mathbb{Q}[alpha]}{mathbb{Z}[alpha]}right|$$ but actually first we can use the corollary telling us that the hypotesis are satisfied if $$p^2not|disc(alpha)$$,
exercise 41 in chapter 2 tells us that in our case $$disc(alpha)=-27^2m$$ and so if $$pneq 3wedge p^2|m$$ we are in the hypotesis of the corollary and thus of the theorem and so we can decompose pR by factoring $$x^3-m$$;

2. In this case the hypotesis of the corollary are not satisfied. We have also that $$p^2|miff p^2|hvee p^2|k^2$$ but since h is squarefree we have that it has to be $$p^2|k^2iff p|kiff pnot|h$$ since they are coprime. Now we can write
$$alpha=sqrt{hk^2}iff alpha^2=sqrt{h^2k^4}iff gamma=frac{alpha^2}{k}=sqrt{h^2k}$$ and we have that $$p^2|h^2kiff p^2|h^2iff p|h$$ which is not true so $$p^2not| h^2k$$.
But now $$p|h^2k=n$$ but $$p^2not|h^2k$$ so $$x^3-n$$ is a p-Eisentstein polynomial and we can use the following theorem to deduce $$pnot| |mathbb{A}cap mathbb{Q}[gamma]/mathbb{Z}[gamma]|$$

Let K = $$mathbb{Q}(alpha)$$ where $$alphain mathbb{A}cap mathbb{Q}[alpha]$$ is the root of an Eisenstein polynomial at p,
with degree n. Then $$p not| |mathbb{A}cap mathbb{Q}[alpha] / mathbb{Z}[alpha]|$$.

## Math Genius: Prime decomposition of pR where R=\$mathbb{A}cap mathbb{Q}[alpha]\$ with \$alpha^5=5(alpha+1)\$, exercise 27 chapter 3 of Marcus

I’m trying to do exercise 27 in chapter of Marcus but it seems to me there is a typo or maybe it’s me not understanding.

The exercise is the following

Let $$alpha^5=5(alpha+1)$$ R=$$mathbb{A}cap mathbb{Q}[alpha]$$.

Let $$pneq 3$$ be a prime of $$mathbb{Z}$$.

Show that the prime decomposition of pR can be determined by factoring $$x^5-5x-5 ; mod; p$$

Do it for p=2

The hint is to use a previous exercise that tells us that the discriminant of $$alpha$$, root of the irreducible polynomial $$x^5+ax+b$$ is $$disc(alpha)=4^4a^5+5^5b^4$$ so in our case the discriminant is $$5^5*3^3*41$$ (isn’t it?).

Another theorem (27 chapter 3 of Marcus Number Fields) tells us that we can decompose pR factoring the minimal polynomial of $$alpha$$ if $$pnot||S/R[alpha]|$$ where S is the integer ring of L and R is the integer ring of K, with L:K.

If I’m not wrong in our case we have $$|S/R[alpha]|=|mathbb{A}capmathbb{Q}[alpha]/mathbb{Z}[alpha]|$$.

A last corollary tells us that if $$p^2not| disc(alpha)$$ then the hypotesis of the theorem are satisfied.

This allows me to say that all the primes but maybe 3 and 5 satisfy the theorem hypotesis, however I don’t know how to say that actually 5 is good but 3 is not.

My last option is to compute an integral basis but it seems a long process so I’m asking if there is another way to do it.

There is also a useful theorem: let $$alpha$$ be an algebraic integer, let $$L=mathbb{Q}(alpha)$$. Assume the minimial polynomial of $$alpha$$ is $$p$$-Eisenstein. Then $$pnmid [O_L:mathbb{Z}[alpha]]$$, where $$O_L$$ is the ring of integers of $$L$$.

IN your case, the minimal polynomial is $$X^5-5X-5$$, which is $$5$$-Eisenstein. So the decomposition of $$5$$ is reflected by the decomposition of s $$X^5-5X-5mod 5.$$

Note that the exercise does not ask to show that it does not work ofr $$3$$. It indeed does not work: modulo $$3$$, $$X^5-5X-5$$ has a decomposition into irreducble factors of the form $$f_1^2f_2$$, while $$3$$ actually does not ramify in $$L$$. A way to see htat would be to compute the discriminant, which is $$5^2cdot 41$$, but I on’t see an easy argument to do so at this moment.

Tagged : /

## Math Genius: How do they check really large primes?

Currently, the largest prime know is a mersenne, $$2^{82,589,933} − 1$$. That’s an $$82,589,933$$-bit number if I am correct. Considering that RSA codes of as low as 1024 bits can be considered safe, how was this number factored to check if it is prime? I can kind of answer that question myself, I am aware of the existence of a special, much faster, prime check for Mersenne primes. But, given a non special number of similar size, would we even be able to check if it was prime? How long would it take? How fast are the fastest prime checking algorithms for non-special form numbers?

The answer is it wasn’t factored to show it was a prime, a special Mersenne prime testing algorithm was used (GIMPS, who found your prime, uses the Lucas-Lehmer test, after checking small factors explicitly). And given a completely arbitrary number of the same size, checking its primality is a lot more work, and not really feasible with current technology as far as I’m aware.

In practice (when encrypting, for example) we use probabilistic prime testing algorithms like the Miller Rabin test whose probability of failing falls off exponentially with the running time. This means we can be fairly certain a number is prime or not if we run it for a reasonable amount of time.

On the other hand, as you mentioned, primes of record breaking sizes are usually generating from special families which have ad hoc primality tests (like Mersenne primes)

After the famous ‘primes is in P’ paper, there are polynomial time algorithms for testing whether a number is prime. According to wikipedia the run time of these is $$O(log(n)^6)$$ and while this is massively faster than actually factoring a number like $$2^{82,589,933}−1$$ the 6th power is still too big to make this feasible on modern computers. On the other hand, these algorithms should be sufficient to quickly check that the large numbers in RSA are not prime (which is not useful for breaking RSA, the algorithms is based on the fact that the number is product of two large prime factors).

Mersenne numbers are special as others have pointed out (the proof of primality is done with the Lucas-Lehmer Test). Fermat numbers are also special and can be proven prime with Pepin’s Test. There are also well known primality tests to use for numbers of the form $$k2^n±1$$ when $$k<2^n$$ (Proth’s Theorem for the plus side, and a related test for the minus side using Lucas Sequences). I recommend reading from here if you are interested in these tests.

RSA-primes on the other hand don’t use deterministic primality tests like the ones above. Instead (in most cases), one uses probabilistic tests (they work well in practice, but cannot prove that a number is actually prime). Such tests include Fermat test, Miller-Rabin, Euler-Jacobi, BPSW, Frobenius, etc.

If provable primes are desired, it is possible to prove RSA-primes ‘prime’, but will come at a timely cost (300-700 digits roughly speaking). The quickest of methods that are used include APR-CL and ECPP. Still, these become impractical (timewise) once the size of the input is about 10k or 50k digits or so, thus there is no current (practical) method to prove such large numbers primes and we must either resort to probable primes (any number), or provable primes which rely on (some) factorization of usually either $$n-1$$, $$n+1$$ or both.

Apart from the arguments mentioned in the others’ answers, one more thing should be said. The GIMPS is a distributed computing project. At the moment, its performance is over 1 000 TFLOPs per second. That’s a huge computing power, comparable to large supercomputers. Except the Lucas-Lehmer test (LLT), they also perform factoring and probable prime testing. Only a small fraction of candidates are subject to LLT. Even so, for the vast majority of composite numbers, their factorization is unknown. This is the main reason why they can check such large numbers.

Tagged :

## Math Genius: All the small primes close together yet again

\$\$
begin{align}
2254 & = 2cdot7cdot7cdot23 \
2255 & = 5cdot11cdot41 \
2256 & = 2cdot2cdot2cdot2cdot3cdot47 \
2257 & = 37cdot61 \
2258 & = 2cdot1129 \
2259 & = 3cdot3cdot251 \
2260 & = 2cdot2cdot5cdot113 \
2261 & = 7cdot17cdot19 \
2262 & = 2cdot3cdot13cdot29 \
2263 & = 31cdot73 \
2264 & = 2cdot2cdot2cdot283 \
2265 & = 3cdot5cdot151 \
2266 & = 2cdot11cdot103
end{align}
\$\$
I this question I pointed something out, of which the foregoing is another instance.

The integer parts of the square roots of all of these numbers are equal to \$47\$, which is the \$15\$th prime, so if we’re checking for primality, we need to search that far and the rest does itself. Now notice which primes \$le47\$ appear above:
\$\$
2,,3,,5,,7,,11,,13,,17,,19,,23,,29,,31,,37,,41,,bullet,,47
\$\$
i.e. all of those first \$15\$ except \$43\$. Hence nearby numbers can be divisible only by small primes that recur frequently or primes bigger than the square root of the number being factored. (In particular \$2272\$ is \$71\$ times a power of \$2\$, and \$2268\$ has no prime factors bigger than \$7\$.)

Is there any reasonable sense it which it could be said that we shouldn’t find it so surprising that this—all those early primes occurring so close together—occurs among numbers as small as these? Should we expect frequent instances of this?

PS: “Small” should probably be taken to mean these numbers are not much bigger than \$47^2=2209\$, where, remember, \$47\$ is the biggest prime number \$le\$ the square roots of these numbers.

As you acknowledge, your example is imperfect in that your set $$S={2254,dots,2266}$$ lacks a multiple of 43. If we take $$p_i=53$$, then, to cover all primes $$q with a range of consecutive integers not all less than $$p_{i-1}{}^2=47^2=2209$$, we need 16 integers, and the range $${2664,dots,2679}$$ will do.

To investigate further, for each prime $$p=p_i$$ I found that range of $$k=k(p)$$ consecutive integers $${n-k+1,dots,n}$$ that covers all primes $$q, minimising $$k(p)$$, subject to $$ngeqslant p_{i-1}{}^2$$.

There are 1229 primes $$p<10000$$. For 258 of them, or about 21%, $$k(p)$$ sets a new record high for $$k$$. Below I list the results for a few of these, where $$k(p)/p$$ also set a record high for $$k/p$$.

$$begin{array}{rrrrr} p&k&n-k+1&n&k/p\ 43&14&1763&1776&0.326\ 103&52&10184&10235&0.505\ 241&161&56970&57130&0.668\ 509&358&254472&254829&0.703\ 1013&783&1023703&1024485&0.773\ 2113&1807&4456626&4458432&0.855\ 5101&4476&25996157&26000632&0.877\ 9241&8441&85369195&85377635&0.913 end{array}$$

There is a general trend upwards in $$k/p$$. Below is another selection where this time I selected some of those $$p$$ where $$k(p)/p$$ is less than all later $$k(q)/q$$ for all $$q>p$$ within the scope of my program run:

$$begin{array}{rrrrr} p&k&n-k+1&n&k/p\ 17&3&285&287&0.176\ 53&16&2664&2679&0.302\ 101&37&9699&9735&0.366\ 229&109&51900&52008&0.476\ 557&301&307268&307568&0.540\ 1031&709&1049190&1049898&0.688\ 2237&1606&4966944&4968549&0.718\ 5011&4084&25093284&25097367&0.815 end{array}$$

Your $$p=53$$ is among these! Even though making an $$S$$ which covers all primes $$q<53$$ needed $$k=16$$, somewhat more than your example which lacked 43, $$k(53)=16$$ gives $$k/papprox0.302$$ which turns out to be a record low.

Whether $$liminf_{ptoinfty} k(p)/p=1$$ I daren’t say, but it appears that way. At any rate, once $$p$$ gets into the thousands, every prime $$p$$ needs a sequence $$S$$ which has (as a proportion) nearly $$p$$ terms.