平方因子を持たない整数

数学において、平方因子を持たない整数（または平方因子を持たない整数）とは、1以外の平方数で割り切れない整数のことです。つまり、その素因数分解には、含まれる各素数に対してちょうど1つの因数があります。例えば、10 = 2 ⋅ 5は平方因子を持たない整数ですが、18 = 2 ⋅ 3 ⋅ 3は平方因子を持たない整数ではありません。なぜなら、18 は9 = 3 ²で割り切れるからです。最小の正の平方因子を持たない数は

すべての正の整数${\displaystyle n}$独自の方法で因数分解できます $${\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},}$$ どこで$q_i$1 と異なる は、互いに素な平方因子を持たない整数です。これはnの平方因子を持たない因数分解と呼ばれます。

平方因子を含まない因数分解を構築するには、 $${\displaystyle n=\prod _{j=1}^{h}p_{j}^{e_{j}}}$$の素因数分解 である${\displaystyle n}$、${\displaystyle p_{j}}$は互いに異なる素数である。このとき、平方因子を含まない因数分解の因数は次のように定義される。 $${\displaystyle q_{i}=\prod _{j:e_{j}=i}p_{j}.}$$

整数が平方数でないのは、${\displaystyle q_{i}=1}$すべての人々のために${\displaystyle i>1}$1より大きい整数は${\displaystyle k}$別の整数の 乗である場合、かつその場合に限り、${\displaystyle k}$すべての約数です${\displaystyle i}$そのため${\displaystyle q_{i}\neq 1.}$

整数の平方因子を含まない因数分解の利用は、その計算が素因数分解の計算と同じくらい難しいという事実によって制限される。より正確には、平方因子を含まない因数分解を計算する既知のアルゴリズムはすべて、素因数分解も計算する。これは、同じ定義を与えることができる多項式の場合とは顕著な違いである。多項式の場合、平方因子を含まない因数分解は完全な因数分解よりも計算が容易であるだけでなく、すべての標準的な因数分解アルゴリズムの最初のステップとなっている。

正方形のない部分${\displaystyle n}$は、すべての素因数の積です。 ${\displaystyle n}$因数分解における指数は${\displaystyle n}$は奇数です。各正の整数${\displaystyle n}$は、可能な限り最大の平方数と平方数を持たない整数 の積として一意に表現できます。${\displaystyle n=m^{2}k,}$ どこ${\displaystyle k}$は、${\displaystyle n}$そして${\displaystyle m}$は の最大約数です${\displaystyle n}$そのため${\displaystyle m^{2}}$はの約数です${\displaystyle n}$。

すべての正の整数${\displaystyle n}$は、強力な数（つまり、すべての素因数の平方で割り切れる整数）と平方因子を持たない整数の積として一意に表現できる。${\displaystyle s}$。 これ${\displaystyle s}$は、割り切れる素数の積です。${\displaystyle n}$第一乗のみで、強力な数は ${\displaystyle n/s.}$

整数の根号${\displaystyle n}$は、その最大の平方因子ではない因数、つまり、のすべての素因数の積です。${\displaystyle n}$これは、${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}}$前の節の表記法において。整数の根号は平方因子を持たない部分よりも小さい場合がある。整数が平方因子を持たないのは、その整数が根号と等しい場合に限る。

要約すると、すべての整数に自然に関連付けられる3つの平方因子が存在します。上記の因子${\displaystyle s,}$平方因子を持たない部分と、最大の平方因子を持たない部分。それぞれが次の因子の因数です。これらはすべて、素因数分解または平方因子を持たない部分分解から容易に導き出せます。 $${\displaystyle n=\prod _{i=1}^{h}p_{i}^{e_{i}}=\prod _{i=1}^{k}q_{i}^{i}}$$ は、の素因数分解と平方因子を含まない因数分解である。${\displaystyle n}$、 どこ${\displaystyle p_{1},\ldots ,p_{h}}$は異なる素数であり、平方因子を持たない部分は $${\displaystyle \prod _{e_{i}=1}p_{i}=q_{1},}$$ 商が平方数となるような平方因子は $${\displaystyle \prod _{e_{i}{\text{ odd}}}p_{i}=\prod _{i{\text{ odd}}}q_{i},}$$ そして最大の平方因子は $${\displaystyle \prod _{i=1}^{h}p_{i}=\prod _{i=1}^{k}q_{i}.}$$

例えば、${\displaystyle n=75600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7,}$1つは${\displaystyle q_{1}=7,\;q_{2}=5,\;q_{3}=3,\;q_{4}=2.}$平方因子でない部分は7であり、商が平方となるような平方因子でない部分は3 ⋅ 7 = 21であり、最大の平方因子でない部分は2 ⋅ 3 ⋅ 5 ⋅ 7 = 210です。

これらの平方因子の計算において、完全な素因数分解の計算よりも高速なアルゴリズムは知られていない。特に、整数の平方因子部分を計算する、あるいは整数が平方因子でないかどうかを判定する多項式時間アルゴリズムは知られていない。 ^{[ 1 ]}対照的に、素数判定 のための多項式時間アルゴリズムは知られている。^{[ 2 ]}

正の整数${\displaystyle n}$は、の素因数分解において、 が平方因子を持たない場合に限り、平方因子を持たない。${\displaystyle n}$指数が 1 より大きい素因数は存在しない。別の言い方をすれば、すべての素因数に対して、${\displaystyle p}$の${\displaystyle n}$プライム${\displaystyle p}$均等に分割できない ${\displaystyle n/p}$。 また${\displaystyle n}$平方因子を持たないのは、すべての因数分解において、${\displaystyle n=ab}$要因${\displaystyle a}$そして${\displaystyle b}$は互いに素である。この定義から直ちに導かれる結論は、すべての素数は平方数を持たないということである。

正の整数${\displaystyle n}$が平方フリーであるのは、位数のすべてのアーベル群が平方フリーである場合に限る。${\displaystyle n}$それらは同型であり、これはそのような群が巡回群である場合に限り成り立つ。これは有限生成アーベル群の分類から導かれる。

整数${\displaystyle n}$は平方因子環が平方因子でない場合に限り平方因子環である。${\displaystyle \mathbb {Z} /n\mathbb {Z} }$（モジュラー算術を参照）は体の積である。これは中国剰余定理と、の形の環が${\displaystyle \mathbb {Z} /k\mathbb {Z} }$フィールドであるのは、${\displaystyle k}$素数です。

すべての正の整数に対して${\displaystyle n}$、 のすべての正の約数の集合${\displaystyle n}$整除性を順序関係として用いると、半順序集合となる。この半順序集合は常に分配束である。ブール代数となるのは、以下の条件を満たす場合のみである。${\displaystyle n}$平方数を含まない。

正の整数${\displaystyle n}$平方フリーであるのは、${\displaystyle \mu (n)\neq 0}$、 どこ${\displaystyle \mu }$はメビウス関数を表します。

メビウス関数の絶対値は平方因子を持たない整数の指示関数である。つまり、nが平方因子を持たない整数であれば| μ ( n ) |は 1 に等しく、持たなければ 0 に等しい。この指示関数のディリクレ級数は

${\displaystyle \sum _{n=1}^{\infty }{\frac {|\mu (n)|}{n^{s}}}={\frac {\zeta (s)}{\zeta (2s)}},}$

ここで、ζ ( s )はリーマンゼータ関数である。これはオイラー積から導かれる。

${\displaystyle {\frac {\zeta (s)}{\zeta (2s)}}=\prod _{p}{\frac {(1-p^{-2s})}{(1-p^{-s})}}=\prod _{p}(1+p^{-s}),}$

ここで、積は素数について取られる。

Q ( x )を1からxまでの間の平方因子を持たない整数の数とします（OEIS : A013928インデックス を1だけずらします）。nが大きい場合、nより小さい正の整数の3/4は4で割り切れず、これらの数の8/9は9で割り切れず、以下同様です。これらの比率は乗法性質を満たすため（これは中国剰余定理から導かれます）、次の近似値が得られます。

${\displaystyle {\begin{aligned}Q(x)&\approx x\prod _{p\ {\text{prime}}}\left(1-{\frac {1}{p^{2}}}\right)=x\prod _{p\ {\text{prime}}}{\frac {1}{(1-{\frac {1}{p^{2}}})^{-1}}}\\&=x\prod _{p\ {\text{prime}}}{\frac {1}{1+{\frac {1}{p^{2}}}+{\frac {1}{p^{4}}}+\cdots }}={\frac {x}{\sum _{k=1}^{\infty }{\frac {1}{k^{2}}}}}={\frac {x}{\zeta (2)}}={\frac {6x}{\pi ^{2}}}.\end{aligned}}}$

この議論は、推定値を得るために厳密に行うことができる（ビッグオー記法を使用）。

${\displaystyle Q(x)={\frac {6x}{\pi ^{2}}}+O\left({\sqrt {x}}\right).}$

証明の概略：上記の特徴付けにより

${\displaystyle Q(x)=\sum _{n\leq x}\sum _{d^{2}\mid n}\mu (d)=\sum _{d\leq x}\mu (d)\sum _{n\leq x,d^{2}\mid n}1=\sum _{d\leq x}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor$ ;}

最後の項がゼロであることに注目すると${\displaystyle d>{\sqrt {x}}}$したがって、

${\displaystyle {\begin{aligned}{\phantom {Q(x)}}&=\sum _{d\leq {\sqrt {x}}}{\frac {x\mu (d)}{d^{2}}}+O\left(\sum _{d\leq {\sqrt {x}}}1\right)=x\sum _{d\leq {\sqrt {x}}}{\frac {\mu (d)}{d^{2}}}+O({\sqrt {x}})\\&=x\sum _{d}{\frac {\mu (d)}{d^{2}}}+O\left(x\sum _{d>{\sqrt {x}}}{\frac {1}{d^{2}}}+{\sqrt {x}}\right)={\frac {x}{\zeta (2)}}+O({\sqrt {x}}).\end{aligned}}}$

リーマンゼータ関数の既知の最大のゼロフリー領域を利用することで、アーノルド・ウォルフィスは近似を改善した^{[ 3 ]}

${\displaystyle Q(x)={\frac {6x}{\pi ^{2}}}+O\left(x^{1/2}\exp \left(-c{\frac {(\log x)^{3/5}}{(\log \log x)^{1/5}}}\right)\right),}$

ある正の定数cに対して。

リーマン予想の下では、誤差項は^{[ 4 ]}に縮小できる。

${\displaystyle Q(x)={\frac {x}{\zeta (2)}}+O\left(x^{17/54+\varepsilon }\right)={\frac {6}{\pi ^{2}}}x+O\left(x^{17/54+\varepsilon }\right).}$

2015年には誤差項がさらに削減され（リーマン予想も仮定して）^{[ 5 ]}

${\displaystyle Q(x)={\frac {6}{\pi ^{2}}}x+O\left(x^{11/35+\varepsilon }\right).}$

したがって、平方因子を持たない数の漸近的/自然密度は次のようになる。

${\displaystyle \lim _{x\to \infty }{\frac {Q(x)}{x}}={\frac {6}{\pi ^{2}}}\approx 0.6079}$

したがって、整数の5分の3以上は平方数を持たない。

同様に、Q ( x , n ) が 1 からxの間のnフリー整数 (例えば、3 フリー整数は立方フリー整数)の数を表す場合、 ^{[ 6 ]}が示されます。

${\displaystyle Q(x,n)={\frac {x}{\sum _{k=1}^{\infty }{\frac {1}{k^{n}}}}}+O\left({\sqrt[{n}]{x}}\right)={\frac {x}{\zeta (n)}}+O\left({\sqrt[{n}]{x}}\right).}$

4の倍数は平方因子4=2²を持たなければならないので^、 4つの連続する整数がすべて平方因子を持たないということはあり得ない。一方、4n+1、4n+2、4n+3がすべて平方因子を持たないような整数nは無限に存在する。そうでなければ、4nと4n+1、4n+2、4n+3のうち少なくとも1つが十分大きなnに対して平方因子を持たない可能性があることを考慮すると、すべての正の整数の半分から有限個を引いた数が平方因子を持たないことになり、したがって

${\displaystyle Q(x)\leq {\frac {x}{2}}+C}$ある定数Cに対して、

上記の漸近推定値とは反対に、${\displaystyle Q(x)}$。

任意の長さの連続する非平方因子整数列が存在する。実際、異なる素数の任意のタプル( p ₁ , ..., p _l )に対して、中国剰余定理は同時合同条件を満たすnの存在を保証する。

${\displaystyle n\equiv -i{\pmod {p_{i}^{2}}}\qquad (i=1,2,\ldots ,l).}$

各n + iはp ² _iで割り切れる。^{[ 7 ]}一方、上記の推定値は${\displaystyle Q(x)=6x/\pi ^{2}+O\left({\sqrt {x}}\right)}$これは、ある定数cに対して、 xと の間に平方因子を持たない整数が常に存在することを意味する。${\displaystyle x+c{\sqrt {x}}}$正のxに対して。さらに、基本的な議論により、置き換えることができます。${\displaystyle x+c{\sqrt {x}}}$による${\displaystyle x+cx^{1/5}\log x.}$^{[ 8 ]} abc予想は、${\displaystyle x+x^{o(1)}}$[ ^{9 ]​}

平方因子を持たない数を無限積として表すと

$\displaystyle \prod _{n=0}^{\infty }(p_{n+1})^{a_{n}},a_{n}\in \lbrace 0,1\rbrace ,{\text{ かつ }}p_{n}{\text{ は }}n 番目の素数}},}$

そうすれば私たちはそれらを取ることができます${\displaystyle a_{n}}$そして、それらをエンコードされたバイナリ数のビットとして使用します。

${\displaystyle \sum _{n=0}^{\infty }{a_{n}}\cdot 2^{n}.}$

平方因子を持たない数42は、 2 × 3 × 7という因数分解を持ち、無限積として2 ¹ · 3 ¹ · 5 ⁰ · 7 ¹ · 11 ⁰ · 13 ⁰と表すことができます。 したがって、数42は、11進数でバイナリ数列として符号化できます...001011。（バイナリの桁は、無限積の順序とは逆になっています。）

すべての数の素因数分解は一意であるため、平方因子を持たない整数の二進数表現もすべて一意である。

その逆もまた真である。すべての正の整数は一意の二進数表現を持つため、この符号化を反転させることで、一意の平方因子を持たない整数に復号化することが可能である。

例えば、今度は正の整数である42から始めると、その2進数表現は となります101010。これは2 ⁰ · 3 ¹ · 5 ⁰ · 7 ¹ · 11 ⁰ · 13 ¹ = 3 × 7 × 13 = 273 にデコードされます。

したがって、平方因子を持たない数の二進数符号化は、非負整数と正の平方因子を持たない整数の集合との間の全単射を表す。

（OEISの配列A019565、A048672、A064273を参照。）

中心二項係数

${\displaystyle {2n \choose n}}$

n > 4の場合、平方因子を持たないことは決してありません。これは 1985 年にAndrás Sárközyによって十分に大きなすべての整数に対して証明され^{[ 13 ]}、 1996 年にOlivier RamaréとAndrew Granvilleによって 4 より大きいすべての整数に対して証明されました^{[ 14 ]}。

約数にt乗を含まない正の整数を「tフリー」と呼ぶことにしよう。特に、2 フリー整数は平方フリー整数である。

乗法関数${\displaystyle \mathrm {core} _{t}(n)}$は、すべての正の整数n を、nをt乗する最大の約数で割った商に写像します。つまり、

${\displaystyle \mathrm {core} _{t}(p^{e})=p^{e{\bmod {t}}}.}$

整数${\displaystyle \mathrm {core} _{t}(n)}$はtフリーであり、すべてのtフリー整数は関数によってそれ自身にマッピングされます${\displaystyle \mathrm {core} _{t}.}$

数列の ディリクレ生成関数${\displaystyle \left(\mathrm {core} _{t}(n)\right)_{n\in \mathbb {N} }}$は

${\displaystyle \sum _{n\geq 1}{\frac {\mathrm {core} _{t}(n)}{n^{s}}}={\frac {\zeta (ts)\zeta (s-1)}{\zeta (ts-t)}}}$。

OEIS : A007913  ( t =2)、OEIS : A050985  ( t =3) およびOEIS : A053165  ( t =4)も参照してください。

• シャピロ、ハロルド・N. (1983).数論入門.オックスフォード大学出版局ドーバー出版. ISBN 978-0-486-46669-9。
• Granville, Andrew; Ramaré, Olivier (1996). "指数和の明示的な境界と平方因子を持たない二項係数の希少性". Mathematika . 43 : 73– 107. CiteSeerX 10.1.1.55.8 . doi : 10.1112/S0025579300011608 . MR 1401709 . Zbl 0868.11009 .   
• ガイ、リチャード・K. (2004).数論における未解決問題（第3 版）.シュプリンガー・フェルラーク. ISBN 978-0-387-20860-2. Zbl 1058.11001 . 
• 「OEIS Wiki」 。 2021年9月24日取得。