Pangkat terkecil dari bilangan prima yang faktorisasinya tidak memiliki jumlah faktor yang berbeda
Masalah
Diberikan prima $p$, temukan yang terkecil $n$ sedemikian rupa sehingga beberapa faktorisasi tidak beraturan $p^n$ memiliki jumlah faktor yang sama.
Faktorisasi tak berurutan adalah faktorisasi yang urutan faktornya tidak relevan dan tidak menyertakan faktor sepele $1$. Perhatikan itu$n\gt 1$ untuk semua bilangan prima $p$ karena bilangan prima hanya memiliki satu faktorisasi tak berurutan.
Contoh
Utama $p=2$. Itu sepele itu$n=2$ untuk $p=2$ karena $2+2=2\cdot 2$. Artinya, faktorisasi tidak berurutan dari$2^2$ adalah $4$ dan $2\cdot 2$, dan keduanya memiliki jumlah faktor yang sama $4 = 2+2$.
Utama $p=3$. Tapi,$n=2$ bukanlah solusi untuk $p=3$ karena $9\ne 3+3$. Tidak juga$n=3$ karena $27\ne 3+9 \ne 3+3+3$. Tidak juga$n=4$ karena $81\ne 27 + 3\ne 9 + 9\ne 9 + 3 + 3\ne 3 + 3 + 3 + 3$. Akhirnya, kami menemukan itu$n=12$ adalah yang terkecil yang cocok, karena terdapat jumlah duplikat faktor berikut:
$$\begin{align}{} 3^{12}&=&27\cdot3^9&=&9^6 &\implies& 27+\sum_{i=1}^{9}3 &=& \sum_{i=1}^{6}9 &=& 54 \\ 3^{12}&=&81\cdot9\cdot 3^6&=&27^4 &\implies& 81+9+\sum_{i=1}^{6}3 &=& \sum_{i=1}^{4}27 &=& 108 \end{align}$$
Perhatikan bahwa jika $p^{n}$ atau bilangan apa pun secara umum memenuhi sifat ini, maka semua kelipatan bilangan itu juga memenuhi itu.
Larutan?
Utama $p\in\mathbb P$. Membiarkan$a(k)$ menjadi yang terkecil $n_k$ mengingat $k$th prime$p_k$. Kita punya:
$$a(k) = 2, 12, 26, 34, 50, 58, 74, 82, \dots$$
Apakah mungkin menemukan dan membuktikan rumus untuk urutan ini?
Saya perhatikan yang berikut tampaknya bertahan sejauh ini: $a(1)=2,a(2)=12,a(k)=4p_k+6,k\ge 3$.
Ini karena faktorisasi tak berurutan berikut:
$$\begin{align} p_k &\quad n &\quad \\ 2 &\quad 2 &\quad (2)(2) &=(2^2) \\ 3 &\quad 12 &\quad (3)^9(3^3) &= (3^2)^6 &\quad (3)^6(3^2)(3^4) &= (3^3)^4 \\ 5 &\quad 26 &\quad (5^2)^{11} (5^4) &= (5)^5(5^3)^7 \\ 7 &\quad 34 &\quad (7)^{15}(7^4) &= (7)^7(7^3)^9 \\ 11 &\quad 50 &\quad (11^2)^{23}(11^4) &= (11)^{11}(11^3)^{13}\\ 13 &\quad 58 &\quad (13^2)^{27}(13^4) &= (13)^{13}(13^3)^{15}\\ 17 &\quad 74 &\quad (17^2)^{35}(17^4) &= (17)^{17}(17^3)^{19}\\ 19 &\quad 82 &\quad (19^2)^{39}(19^4) &= (19)^{19}(19^3)^{21}\\ \end{align}$$
Perhatikan bahwa bilangan prima $p_k\ge 5$ ikuti pola berikut:
$$ (p^2)^{2p+1}(p^4) = (p)^{p}(p^3)^{p+2} \implies (p^2)\cdot(2p+1)+(p^4) = (p)\cdot p+(p^3)\cdot(p+2) $$
Ini memberi kita batas atas $a(k)\le 4p_k+6$ karena polanya berlaku untuk semua bilangan asli.
Kesetaraan itu terbukti secara komputasi untuk beberapa bilangan prima kecil (seperti yang Anda lihat di atas).
Bisakah kita membuktikan bahwa kesetaraan selalu berlaku? Yaitu bisa kita buktikan$a(k)\ge 4p_k+6, k\ge 3$ ?
Artinya, dibiarkan membuktikan bahwa semua faktorisasi tak berurutan dari bilangan bentuk
$$ p^{4p+5} $$
memiliki jumlah faktor yang berbeda untuk semua bilangan prima $p\ge 5$.
Dengan kata lain, kita perlu membuktikannya $\text{A001055}$$(p^{4p+5})$ $=$ $\text{A069016}$$(p^{4p+5})$.
Atau mungkin ada bilangan prima $p$itu adalah contoh tandingan? Yaitu$p_k : a(k)\lt 4p_k+6$ ?
Jawaban
Catatan: solusi saya cukup panjang dan mengandung banyak kasus, jadi beberapa kesalahan tidak dapat dihindari. Beri tahu saya jika ada yang perlu dijelaskan.
Membiarkan $n$ menjadi angka terkecil sehingga $p^n$memiliki dua faktorisasi tidak berurutan dengan jumlah faktor yang sama. Kami akan menganggap itu$n \le 4p+5$ dan mendapatkan kontradiksi.
Dilambangkan dengan $A=(p^{a_1})^{n_1}\dots (p^{a_k})^{n_k}$ dan $B=(p^{b_1})^{m_1}\dots(p^{b_l})^{m_l}$ dua faktorisasi tidak beraturan, dengan $a_1 > \dots > a_k$ dan $b_1 > \dots > b_l$. Tanpa kehilangan keumuman, asumsikan itu$A$ memiliki kekuatan yang lebih tinggi $p$, yaitu itu $a_1 \ge b_1$.
Pengamatan 1: $\{a_1,\dots,a_k\} \cap \{b_1,\dots,b_l\}=\emptyset$.
Ini karena jika $a_i=b_j$ untuk beberapa $i,j$, lalu kita bisa mengurangi $p^{a_i}$ dari kedua faktorisasi untuk mendapatkan dua faktorisasi tak berurutan dengan jumlah yang sama $p^{n-a_i}$, kontradiksi minimal $n$.
Pengamatan 2: $a_1 \le 5$.
Ini berasal dari mempertimbangkan persamaan $$\begin{equation}\label{eqn1} b_1m_1+\dots+b_lm_l=n \qquad (1)\end{equation}$$ dan $$ \begin{equation} m_1p^{b_1}+\dots+m_lp^{b_l}=n_1p^{a_1}+\dots+n_kp^{a_k}\qquad (2)\end{equation}$$ Jika Anda menyelesaikan maksimum LHS dari (2) diberikan (1) (dan dengan $m_j \in \mathbb{R}$ sebaliknya), maka maksimum dicapai pada $m_1=n/b_1$ dan $m_j=0$ untuk semua $j \ge 2$, dengan nilai maksimumnya $\frac{n}{b_1}p^{b_1}$. Di sisi lain, Kanan dari (2) memberikan batas bawah$p^{a_1}$, maka kita harus memilikinya $$ \frac{n}{b_1} p^{b_1} \ge p^{a_1} \iff n \ge b_1 p^{a_1-b_1} .$$ Sejak $n \le 4p+5 \le p^2$ untuk $p \ge 5$, kami punya itu $$ a_1-b_1=2, b_1=1 \qquad \text{or} \qquad a_1-b_1=1, b_1 \le 4$$ dan dalam kedua kasus tersebut $a_1 \le 5$.
Kami sekarang mempertimbangkan berbagai kasus $a_1 \in \{2,3,4,5\}$, dengan $a_1=4$ menjadi yang tersulit.
Jika $a_1=2$, kemudian $b_1=1$ dan kami mendapatkan dua faktorisasi $(p^2)^{n/2}$ dan $p^n$. Mereka tidak memiliki jumlah faktor yang sama untuk$p>2$.
Jika $a_1=3$, maka kami memiliki opsi berikut:
- $a_2=2$, $b_1=1$. Kami mendapatkan dua faktorisasi$(p^3)^{n_1}(p^2)^{n_2}$ dan $p^n$. Mereka tidak memiliki jumlah yang sama sejak itu$$np \le (4p+5)p < p^3$$ untuk $p \ge 5$.
- $a_2=1$, $b_1=2$. Kami mendapatkan dua faktorisasi$(p^3)^{n_1}p^{n_2}$ dan $(p^2)^{n/2}$. Sejak$$\frac{n}{2}p^2 \le \frac{4p+5}{2}p^2 < 3p^3$$ untuk $p \ge 5$, kami punya itu $n_1 \in \{1,2\}$. Salah satu nilai tidak menghasilkan jumlah yang sama.
- $b_1=2$, $b_2=1$. Kami mendapatkan dua faktorisasi$(p^3)^{n/3}$ dan $(p^2)^{m_1}p^{m_2}$. Kemudian$$ m_1 p^2+m_2p \le \frac{n}{2}p^2 < \frac{n}{3}p^3. $$
- $b_1=2$. Kita mendapatkan$(p^3)^{n/3}$ dan $(p^2)^{n/2}$, yang jumlahnya tidak sama.
- $b_1=1$. Kita mendapatkan$(p^3)^{n/3}$ dan $p^n$, yang jumlahnya tidak sama.
Jika $a_1=5$, kemudian $b_1=4$seperti yang telah kami bahas di atas. Dengan argumen yang sama, kita bisa melihat itu$$ m_1p^4+\dots +m_l p^{b_l} < 2p^5 $$ untuk semua pilihan $m_1,\dots,m_l$, jadi $n_1=1$, dan $$ m_1p^4+\dots +m_l p^{b_l} \ge p^5 $$ hanya bila $m_1 \ge p$. Oleh karena itu, kami memilikinya$$ A = (p^5)\cdot(\text{unordered factorization of }p^{n-5}) \quad \text{and} \quad B= (p^4)^p\cdot(\text{unordered factorization of }p^{n-4p}).$$ Secara khusus, ini menyiratkan itu $n \in \{4p, \dots, 4p+5\}$. Beberapa pemeriksaan lagi menunjukkan bahwa untuk itu$n$, tidak ada faktorisasi $p^{n-5}$ memiliki jumlah faktor yang sama seperti faktorisasi apa pun $p^{n-4p}$.
Jika $a_1=4$, kemudian $b_1=3$ dari argumen dalam Pengamatan 2. Dengan menggunakan argumen yang sama seperti dalam kasus di atas, kami menyimpulkan bahwa $n_1=1$ dan $m_1 \ge p$. Oleh karena itu, kami punya$$ A = (p^4)\cdot(\text{unordered factorization of }p^{n-4}) \quad \text{and} \quad B= (p^3)^p\cdot(\text{unordered factorization of }p^{n-3p}).$$ Tetap mempertimbangkan opsi berikut untuk $a_2,\dots,a_k$:
- $a_2=1$. Lalu jika$A=(p^4)p^{n-4}$ dan $B=(p^3)^{m_1}(p^2)^{m_2}$ memiliki jumlah yang sama, kita harus memiliki $$ (n-4)p=(m_1-p)p^3+m_2p^2 \ge \frac{n}{2} p^2,$$ yang salah $p \ge 5$ dan $n \le 4p+5$.
- $a_2=2$, $a_3=1$. Kemudian$A=(p^4)(p^2)^{n_2}p^{n_3}$ dan $B=(p^3)^{n/3}$. Jika jumlahnya sama, maka$$ (n/3-p)p^3=n_2p^2+n_3p$$ jadi secara khusus $p \mid n_3$. Sejak$n_3 \le n-4 \le 4p+1$ kita harus punya $n_3 \in \{p,2p,3p,4p\}$. Memasukkan setiap nilai$n_3$ dan $n_2=n-4-n_3$ ke dalam persamaan, kami menemukan bahwa tidak ada yang menghasilkan nilai integer $n$.
- $a_2=2$. Kemudian$A=(p^4)(p^2)^{(n-4)/2}$ dan $B=(p^3)^{m_1}p^{m_2}$. Jika jumlahnya sama, maka$$\frac{n-4}{2}p^2=(m_1-p)p^3+m_2p$$ begitu $p \mid m_2$, dan serupa dengan yang kami dapatkan di atas $m_2 \in \{p,2p,3p\}$. Sekali lagi, memasukkan setiap nilai$m_2$ dan $m_1=n-m_2$ ke dalam persamaan, kami menemukan bahwa tidak ada yang menghasilkan nilai integer $n \le 4p+5$.