整数論の問題を出し合うスレ

c[n+1]=8c[n]-7で定義される数列c[0],c[1],c[2],...に対し
c[1],c[2],....が全て合成数になるような素数c[0]を2つ求めよ
って問題が東工大AOで出たが
c[0]=2ならc[n]は1+2^nで割り切れる、c[0]=7ならc[n]は7で割り切れるから
2と7が答えになるけど
それ以外にどんな素数が答えになるのか

以下の等式をみたす整数の組(a,b)をすべて求めよ
a^3+3ab+b^3=1

以下の等式をみたす整数の組(a,b)をすべて求めよ
a^{3n}+3a^nb^n+b^{3n}=1

>>545
k=c[0]-1とおくと c[n]=k*2^(3n) +1 だから、
kがSierpinski数であれば c[n] はすべて合成数だけど、
現在知られているSierpinski数の求め方ではk+1が合成数となってしまうので使えないね。
（Sierpinski数でなくても同様の求め方により、例えば k≡83 (mod 195)であれば
k*8^n +1は常に合成数になるが、k+1は3の倍数になってしまう)

>>548
Sierpinski数なんてのがあったのか
東工大の問題作った人の脳の隅にもSierpinski数があったのかな

>>546
a^3+3ab+b^3-1=(a+b-1){(a-b)^2+(a+1)^2+(b+1)^2}/2 だから、
a^3+3ab+b^3=1 ⇔ a+b-1=0 または a=b=-1
(a, b) = (-1, -1), (t, 1-t) (t:整数)

>>547　n は 2 以上の正整数と決め打っておく。
上に述べたことから、a^n+b^n=1 または a^n=b^n=-1

n が偶数のとき、a^n, b^nはともに非負整数であるから (a, b) = (0, ±1), (±1, 0)。

n が 3 以上の奇数のとき、a^n+b^n=1 とすると a, b がともに 0 以下になることはないので、
たとえば a>0 であるとすると b^n = 1-a^n ≦0、よって 0≧b＞-a で a+b は 1 の約数だから a+b=1。
c=-b とおくと 0≦c, a=1+c, a^n-c^n=1 だから、
0 = (1+c)^n - c^n - 1 = C(n-1,1)*c+C(n-1,2)*c^2+...+C(n-1,n-1)c^(n-1)。
右辺の各項は非負であるから、c = 0 でなければならない。
以上より、(a, b) = (-1, -1), (1, 0), (0, 1)。

>>523 の類題

〔出題345〕
　方程式 3^x + 4^y = 5^z の自然数解をすべて求めよ。（だるまにおん）


http://www.casphy.com/bbs/test/read.cgi/highmath/1204794089/345
　casphy - 高校数学 - 整数問題

>>523 の類題

〔出題319〕
　5^x + 3^y = 2^z を満たす整数(x,y,z)の組を全て求めよ。(arccoversinh)

http://www.casphy.com/bbs/test/read.cgi/highmath/1204794089/319
　casphy - 高校数学 - 整数問題

>>551,552
同スレ内で既出。きちんと読め。カス野郎。

453, 456 を参照しる。

>>553
どうして そういうことを言うのかなあ…

5^x + 3^y = 2^z
5u+3v=1
5-6=-1
u2^z=(-1+3m)2^z=5^x-1
v2^z=(2-5m)2^z=3^y-1
2^z(5u+3v)=2^z
x=log((-1+3m)2^z)/log5+1
y=log((2-5m)2^z)/log3+1
(-1+3m)2^z=5^s z=0,m=(5^s+1)/3,x=s+1
m=(2-3^k)/5=(5^s+1)/3
1=3^k+1+5^s+1
k=log(1-5^s+1)/log3-1
y=log(1-5^s+1)/log3

>>487
　「y^2 = x^3 - 4 の有理点 と 整点」[2006.07.01]
　"Rational points and integral points on elliptic curve: y^2 = x^3 -4"
　整点:　(2,±2), (5,±11),
　有理点: (106/(3^2), ±1090/(3^3)), (785/(22^2), ±5497/(22^3)), (151322/(61^2), ±58862702/(61^3)), ･･････
　判別式 Δ = -6912 = -2^8･3^3,
　j = 0,
　導手 N = 432,

[参考書]
　Nigel P. Smart, "The algorithmic resolution of Diophantine equations", LMSST 41, Cambridge University Press, (1998),
　243pp
　£16.95
　ISBN 0-521-64633-2.

http://www.kaynet.or.jp/~kay/misc/ix3m4.html

>>461
〔補題〕
　n≧2,　(5^n) | (7^k -1) ならば、4･5^(n-2) | k,

(略証)
　7^4 - 1 = (7^2 - 1)(7^2 + 1) = 96･5^2,
　k≡0 (mod 4) のとき　7^k - 1 ≡ 7^0 - 1 =　 0 (mod 96･5^2)
　k≡1 (mod 4) のとき　7^k - 1 ≡ 7^1 - 1 =　 6 (mod 96･5^2)
　k≡2 (mod 4) のとき　7^k - 1 ≡ 7^2 - 1 =　48 (mod 96･5^2)
　k≡3 (mod 4) のとき　7^k - 1 ≡ 7^3 - 1 = 342 (mod 96･5^2)
∴　kは4の倍数に限る。
∴　7^k - 1 = (7^4)^(k/4) - 1 = (1 + 96･5^2)^(k/4) - 1 = 24k･5^2 + (k(k-4)/2)･(24^2)･5^4 + ････

ところで題意より、7^k -1 中の5のベキ指数は n≧2,
　7^k - 1 ≡ 0　(mod 96･5^n),

∴　24k･5^2 ≡ 0　(mod 96･5^n)
　k ≡ 0　(mod 4･5^(n-2))
　4･5^(n-2) | k,
(終)

〔問題〕
　x^3 + y^3 + z^3 = 52,　を満たす整数(x,y,z) をすべて求む。

例　(x,y,z) = (60702901317, 23961292454, -61922712865)
　x+y = 84664193771 = 521*162503251,
　z^3 ≡ 52 (mod 521)　より z≡-290 (mod 521)

　

>>487　>>556

Mordell曲線
　y^2 = x^3 -4　　････････ (E)
上に有理点 P1: (x1,y1) があるとき、 (y1≠0)
P1 でのEの接線の傾きは M = (3x1^2)/(2y1), 接線は
　y = y1 + M(x-x1)　　･･･････ (L)
(E) と (L) の交点を考える。
　{y1 + M(x-x1)}^2 = x^3 - 4,
　0 = x^3 -(M^2)x^2 + ････
∴　この３次方程式は x1 (重根) のほかに M^2 - 2x1 を解にもつ。　
　x2 = M^2 - 2x1,
　y2 = M^3 -3M･x1 + y1,
P2: (x2,y2) もまたE上の有理点である。
このようにして、E上に無限に多くの有理点があることを示せる。
例　(2, ±2) → (5, ±11) → (785/(22^2), 干5497/(22^3)) → ･･････

[問]
pを、4を法として1に合同であるような素数とする。
p=4n+1とすると、nはpを法として4乗剰余であること、つまり
a^4≡n (mod p)を満たす整数aが存在することを証明せよ。

>>434 >>551

mod 24 で考える。
　x=0　⇒　2^x = 1,
　x=1　⇒　2^x = 2,
　x=2　⇒　2^x = 4,
　x奇数、x≧3　⇒　2^x ≡ 8　(mod 24)
　x偶数、x≧4　⇒　2^x ≡ 16 (mod 24)

　y=0　⇒　3^y = 1,
　y奇数　⇒　3^y ≡ 3　(mod 24)
　y偶数　⇒　3^y ≡ 9　(mod 24)

　z奇数　⇒　5^z ≡ 5　(mod 24)
　z偶数　⇒　5^z ≡ 1　(mod 24)

>>434 >>551

>>561 より、題意を満たすのは 次の3つの場合。
　(a)　x=1、y奇数、z奇数
　(b)　x=2、y=0、z奇数
　(c)　x、y、z のすべて偶数（x≧4、y≧2）、

　(a) は (x,y,z) = (1,1,1)　　>>453
　(b) は (x,y,z) = (2,0,1)
　(c) y=2y'　z=2z' とおく。
　　2^x = 5^z - 3^y = (5^z' + 3^y')(5^z' - 3^y'),
　5^z' + 3^y' = 2^(x-w),
　5^z' - 3^y' = 2^w,
辺々引いて 2で割る。
　3^y' = 2^(x-w-1) - 2^(w-1),
∴　w = 1,
一方、3^y' ≡ 1, 3　(mod 8)
∴ 2^(x-2) ≡ 2, 4　(mod 8)
　xは偶数ゆえ x = 4,
∴　3^y' = 2^(x-2) - 1 = 3,
∴　y'=1, y=2,
∴　z'=1, z=2,
∴　(x,y,z) = (4,2,2)

〔系〕　>>523 も同様。

ぬるぽ

>>560
aをpで割り切れない整数とするとき、(a/p)をルジャンドルの記号とする。

pが4を法として1に合同であるような素数だから
1=(-1/p)=(-4/p)だからx^2≡-4 (mod p)が解sを持つ
{ {s/2}+1}^2≡s^2/4 +s+1≡s，このとき、{s/2}+1=tとおくとt^4≡-4 (mod p)
明らかにtはpと互いに素である
1≡-4n≡t^4*n (mod p)よってn≡(1/t)^4 (mod p)となるから
a^4≡n (mod p)を満たす整数aが存在することがいえた。

>>562
ガッ

〔問題〕
　(2^n + 1)/n^2 が整数となるような自然数ｎを全て決定せよ。

http://science6.2ch.net/test/read.cgi/math/1254690000/163-166
　面白い問題スレ１６

参考書
　吉永良正「数学・まだこんなことがわからない−素数の謎から森理論まで−」(講談社ブルーバックス) (1990/11)
　ISBN: 406132845X, ISBN-13: 978-4061328457

　秋山 仁＋ﾋﾟｰﾀｰ･ﾌﾗﾝｸﾙ 共著「完全攻略　数学オリンピック」日本評論社 (1991/11/20)
　ISBN: 4-535-78185-0　　　p.68〜70 (ﾐｽﾌﾟﾘﾝﾄ有り) 　

>>564　当スレ >>229にて既出、 解答の方針は >>234で示されています。

>>563　(1+√(-1))^4=-4ということですね。
簡単な関連問題を。

[問]
pは奇素数、4n=p-(-1)^{(p-1)/2}とする。
n^n≡1(mod p)となる必要十分条件は
p≡1(mod 4)またはp=3であることを証明せよ。

pは奇素数

>>565
p≡1 (mod 4)のとき
p=4n+1
>>563より、n≡a^4 (mod p) をみたす整数aが存在する。
このときaとpは互いに素だから、
n^n≡a^(4n)≡a^(p-1)≡1 (mod p)となることがいえる。

p≡3 (mod 4)のとき
p=4n-1だから1≡4n (mod p)となる
p≡7 (mod 8)のとき
b^2≡2 (mod p)をみたす整数bが存在するから4≡2^2≡b^4 (mod p)
p≡3 (mod 8)のとき
b^2≡-2 (mod p)をみたす整数bが存在するから4≡(-2)^2≡b^4 (mod p)

1≡b^4*n (mod p)とかける
bとpは互いに素だからn≡{1/b}^4 (mod p)

したがってn≡c^4 (mod p)をみたす整数cが存在する。
cとpは互いに素だから、n^n≡c^(4n)≡c^(p+1)≡c^2 (mod p)
だからn^n≡1 (mod p)となるのはc^2≡1 (mod p)よりn≡1 (mod p)がいえる。
明らかに1≦n＜4n-1=pだから、n≡1 (mod p)となるのはn=1の場合に限られる。

N = 4^545 + 545^4 が素数であることを証明せよ。

>>568
問題あってる？桁数大杉じゃね？

>>568
4^545≡2 mod 73
545^4≡71 mod 73
よってNは73で割り切れる

9677の倍数でもある

〔問題〕
カレン数の中に素数が無限に存在するか？

Ｃ_n = n･2^n + 1 という数式で表される数をカレン数（Cullen number) という。
ほとんどのカレン数は合成数である一方、カレン素数も無数にあると予想されている｡
Ｃ_n が素数となる n は以下の16個が知られている。
n = 1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881, ……
Ｃ_n　が素数となる n が無限個あるか、という問題が歴史的な問題である。

http://ja.wikipedia.org/wiki/カレン数

〔問題〕
　k･2^n + 1 （k,nは自然数）の形の素数は無限に存在するか？



フェルマー数 F_n = 2^(2^n) + 1 の因数は k･2^(n+2) + 1　(k≧3) の形をしている(Lucas)。
フェルマー数はどの二つも互いに素である。

http://メモ.jp/dictionary/D1007/364.html

>>560
(-1)=g^{(p-1)/2}であり、2^(-1)=g^k を満たす整数kが取れるので、
問題は (p-1)/4 と kのパリティが等しいことを示すのと等価。
kが偶数 ⇔ -2は平方数 ⇔ (p-1)/4は偶数。　これより示せた。

難しいと思われる問題を投下。

「可逆元をちょうど11個持つような環は存在するか」

>>573

〔補題〕p | F_n のとき、p = k･2^(n+1) + 1 (kは自然数)の形
(略証)
　2^(2^n) = F_n - 1 ≡ -1　(mod p)
　2^{2^(n+1)} = {2^(2^n)}^2 = (F_n - 1)^2 ≡ (p-1)^2 ≡ 1　(mod p)
　2^r ≡ 1 (mod p)
を満たす最小の自然数をrとおく。　　(2の位数)
　2^m ≡ 1　⇔　r | m,
　r | 2^(n+1)　より r=2^k, (k≦n+1)
　r | 2^n　でないから k=n+1, r=2^(n+1),
一方、フェルマーの小定理より　2^(p-1) ≡ 1 (mod p)
∴　r | p-1,
∴　p = k･r + 1,　(終)

〔補題〕
　フェルマー数 F_m = 2^(2^m) + 1,　はすべて互いに素。
(略証)
　F_m･(F_m - 2) = F_{m+1} - 2　より
　F_(n-1) | F_n - 2 | F_{n+1} - 2 ｜ …… | F_m - 2 | ……
また、定義より F_m は奇数である。　(終)

〔系〕　nが自然数のとき、等差数列 {k･(2^n) + 1} の中に素数が無限にある。

http://www.casphy.com/bbs/test/read.cgi/highmath/1204794089/383-387
　casphy - 高校数学 - 整数問題
http://messages.yahoo.co.jp/bbs?.mm=GN&action=m&board=1835554&tid=a1vagbfta4acl58ba4kb8badfa49a4ka1a3a1wbf7bftbc0a1aaa1aa&sid=1835554&mid=1&first=1
　Yahoo!掲示板 - 科学板 - 数学カテ - 「素数が無限に存在する！」新数式 トピ

>>573
任意の奇素数 p について、p-1 は偶数、よって p-1 = k*2^n （k はある奇数、n はある正整数）と書ける。
従って、その問題は k または n に何らかの条件をつけないと詰まらないものだろう。

たとえば n を1つ固定し k をパラメータにとるとすれば、
引き合いに出されているLucasの定理より、F_m (m≧n-2)の素因数が条件を満たし、
これは無限に存在する。
牛刀的だが、Dirichletの算術級数定理を用いてもいい。

それでは逆に、正整数 k を1つ固定して考えるとき、k*2^n + 1 が素数であるような
正整数 n は無限に存在するのだろうか。
kが1または2のべきの場合はFermat素数を求めることになるが、これは周知の通り未解決問題である。
また、適当にkを選べば k*2^n + 1 がいかなる正整数 n についても
素数とならないことがSierpinskiによって示されている。（本スレ >>77, >>78 を参照）

>>577
lucasの定理とか少し大袈裟な気が。
そんなもん、(2/p)の値をみれば明らか。

>>578
どこから(2/p)が出てくるんだ…？
具体的に、たとえば1024k+1の形の素数が無限に存在することを示すのに
「(2/p)の値をみれば明らか」って言われても意味不明。

[命題]
任意に整数n≧2を与えるとき、
F_nの任意の素因数pに対して、
v_2(p-1)≧n+2 が成立する。

お宅はこれを大袈裟にlucasの定理とかいっているわけよね。
この命題が正しいことは(2/p)をみれば明らかといっているわけ。

まあ、意味不明と言われたからには証明の概観を書くとするか。
まず、お宅が既に書いたように、v_2(p-1)≧n+1 はいえたわけよね。
n≧2だから、とくに、(2/p)= +1 がいえるわけ。
これから、2^((p-1)/2) = +1　・・・(*) がいえるね。
で、お宅が既に示したように、ord_p(2)= 2^(n+1) だから、
(*)より、2^(n+1)|(p-1)/2　がいえるわけ。はい終わり。

こんな底辺レベルな書き込みしてしまってすみません。
スレ汚しすみませんでした！

定理なんて大袈裟なものでもなんでもないが。
フェルマーの小定理より(>>60)とか大袈裟だってか。

>お宅はこれを大袈裟にlucasの定理とかいっているわけよね。

lucasの定理って>>577が言い出したんじゃなくて>>573に書いてあるじゃん。
(２ちゃんで「お宅」なんて使う奴はじめて見た)

「任意の自然数ｌ、ｍ、ｎに対して、
（ｍ＋ｌ）Ｃｌ＊（ｍ＋ｌ＋１）Ｃｌ＊・・・＊（ｍ＋ｌ＋ｎ−１）Ｃｌは
ｌＣｌ＊（ｌ＋１）Ｃｌ＊・・・＊（ｌ＋ｎ−１）Ｃｌで割り切れる」

>>583
m=1の時を示して、それを使ってmに関する数学的帰納法

m=1の場合は以下の式から成り立つ
Π[k=0,n-1] C[k+l+1,l] = C[n+l,l] Π[k=0,n-1] C[k+l,l]

>>584
mに関する帰納法ではうまく運ばないはず・・・。
mでの成立を仮定しても、それがm+1で活かせない。C［m+l+n,l］/C［m+l,l］が
整数であることを言わないといけないが、それができない。
根本的に違う解法の気がするが、難しい・・・。

>>583
ルジャンドルの等式を用いて、簡単な解析をすればでてくる。
ルーチンワーク。それ以外の方法に興味があるかもしれない。

>>586
なんだそれ？そもそもぐぐっても
ルジャンドルの多項式しかヒットしないけど・・・。
ルジャンドルの多項式の漸化式を使うのか？

たぶんだけど、
v_p(n!) = Σ[n/p]　が成立するというものでは。

ここに Legendre's Identity と紹介してあるね。
http://www.jstor.org/pss/2316661

たしかに上の等式は問題を床関数の解析におとしこむね。
でも、床関数の解析がいつも簡単だとはおもわないけどね^^;
すくなくとも、この問題だと、ΣΣを評価することになると。

素因数ｐの個数っていう等式でしょ？
そこまでは分かるが・・・
俺としては、583の命題の持つ美しい関係に感動する位だ。
任意の自然数という条件もすばらしい・・・。

普通に高坊でもできる

>>575
可逆元をちょうど11個持つような環は存在しない。

(証明)
Rは|R×|=11である環と仮定する。Rの乗法単位元をeとおく。位数が素数なので、R×は巡回群。R×=<a>とする。

(-e)^2=eだから、-e∈R×で、その位数は1または2だが、11の約数だから位数は1、
つまり-e=eでなければならない。よって2e=0だからRの標数は2。
すると(e+a+a^2)(a+a^2+a^4+a^5+a^7+a^8+a^10)=eだからe+a+a^2∈R×、
よってある整数n (0≦n≦10)があって、e+a+a^2=a^nと書ける。

F_2を標数2の素体とし、fをf(1)=e、f(X)=aで定義される、F_2[X]からRへの環準同型写像とする。
p(X)=1+X+X^2-X^n∈F_2[X]、q(X)=X^11-1∈F_2[X]とおくとf(p)=f(q)=0だから(p,q)⊂Ker(f)。
F_2[X]はPIDだから、イデアル(p,q)は単項で(s)と表されるが、
一方、p(1)=0より(X-1)|p(X)で、また、r(X)=X^10 +X^9 +...+X+1 とおくとq(X)=(X-1)r(X)であり、
r(X)はF_2[X]において既約(※)で、さらにr≠pだから、結局s(X)=X-1。
ところが(s)⊂Ker(f)だから0=f(s)=a-e、つまりa=eとなり、aのとり方に反する。(証明終)

(※)
r(X)=X^10+X^9+...+X+1がF_2[X]で既約であることは、rがF_2[X]の5次以下の既約元で
割り切れないことをみればよい。F_2[X]の5次以下の既約元は次の14個であることはすぐにわかる。
1次：X, X+1、2次：X^2+X+1、3次：X^3+X+1, X^3+X^2+1、4次：X^4+X+1, X^4+X^3+1, X^4+X^3+X^2+X+1、
5次：X^5+X^2+1, X^5+X^3+1, X^5+X^4+X^3+X^2+1, X^5+X^4+X^3+X+1, X^5+X^4+X^2+X+1, X^5+X^3+X^2+X+1

>>591
すばらしいです！
そんな初等的な方法があるものなんですね。
私は傍らから考えてはいましたが...。

>>r≠pだから
ここは q≠p だから の間違いですよね。
または deg(p)＜11 だからってことでしょうね。

850

[問題]
p, qを相異なる素数とし、F_p=Z/pZを標数pの素体とする。
F_p上の多項式環F_p[X]の元f_q(X)=(X^q -1) /(X-1) = Σ[k=0〜q-1] X^kが既約である必要十分条件は、
p mod qがZ/qZの原始根であることを証明せよ。

標数0の場合はEisensteinの判定条件により、任意の素数qについてf_q(X)がQ上既約であることが示されるが、
標数正の場合はどうかという問題。これを使えば、>>591のr(X)がF_2上既約であることが簡単に示せる。