12111004

NO.7-1　余りの問題

問題

 98 ： ◆fV8WklhOUQ ：2008/10/31(金) 00:32:40.44 ID:ciaCpCcqO
   a,b,cは1<a<b<cを満たす整数で
   (ab-1)(bc-1)(ca-1)はabcで割りきれる
   このときa,b,cの組を求めよ

解答

...

(a,b,c)=(2,3,5)

解説

(ab-1)(bc-1)(ca-1)=(ab^2c-b(a+c)+1)(ca-1)

=a^2b^2c^2-abc(a+c)+ca-ab^2c+ab+bc-1

=abc(abc-(a+b+c))+ab+bc+ca-1

これがabcで割り切れるので

(abc)k=ab+bc+ca-1とあらわされる。

変形して、

k+1/abc=1/a+1/b+1/c≦1/2+1/3+1/4=13/12で

k＝1か0と分かる。

(1)k=1の時

a=3の時、1/a+1/b+1/c≦1/3+1/4+1/5=47/60となるから

a=2となる

abc=ab+bc+ca-1

bc-2(b+c)+1=0

(b-2)(c-2)=3

b=3,c=5に決定する。よって(2,3,5)

(2)k=0の時

ab+bc+ca=1

2≦aなのでこれを満たすa,b,cは存在しない。

これより、(a,b,c)=(2,3,5)

NO.7-2 n次式の余り

問題

 1 ：以下、名無しにかわりましてVIPがお送りします：2008/11/13(木) 00:31:04.71 ID:gHadZh570
   n（n=3,4,……）に対して、x^nをx^2 - x - 1で割った余りax+bの係数aとbは互いに素であることを証明せよ 

解答

...

フィボナッチ数列第n項をF(n)と表す。(F(1)=1,F(2)=1,F(n+2)=F(n+1)+F(n))

n≧3の時整式の剰余より

x^n=(x^2-x-1)(x^(n-2)+x^(n-3)+2x^(n-4)+3x^(n-5)+5^x(n-6)+…+F(n-3)x^2+F(n-2)x+F(n-1))+(F(n-2)+F(n-1))x+F(n-1)となる。

よってa=F(n)=F(n-1)+F(n-2),b=F(n-1)。

F(n)とF(n-1)がn≧3について互いに素になることを示す。

F(n)-F(n-1)の最大公約数が2以上と仮定する。

F(n)-F(n-1)=F(n-2)より、それならF(n-2)についても同様の約数を持つ。

これはn-2=2の時も言えることになるがF(2)=1より矛盾。

よってF(n)とF(n-1)は互いに素よりn≧3の時にaとbは互いに素。

解説

この問題は、>>1によると東大の過去問らしいです。

でも、整式の割り算の横計算ができれば超簡単ってわけではありませんが解きやすくなります。

NO.7-3　二乗した数の余り

問題

 29 ：以下、名無しにかわりましてVIPがお送りします：2008/11/29(土) 18:20:26.13 ID:XJP+DC730
   制限時間16分　難易度4（実戦応用）
   2≦ｘ≦100、4≦ｙ≦102を満たす整数ｘ、ｙを5で割ったときの余りをそれぞれ、
   Ｘ、Ｙとする。このとき、ｘ＾2＝（5ｍ＋Ｘ）＾2、ｙ＾2＝（5ｎ＋Ｙ）＾2とする。
   ｘ、ｙを共に5以下だとおくと、ｘ＾2＋ｙ＾2を5で割った余りは{ア}、{イ}、{ウ}、{エ}
   のいずれかになる。6583＾5を5で割った余りは{オ}で、6583＾5と2（ｘ＾2＋ｙ＾2）が共通の余りを持つようなｘ、ｙの組は全部で{カキクケ}通りある。

解答

...

(ア)(イ)(ウ)(エ)0,1,2,4　(オ)3　(カ)1560

解説

(ア)(イ)(ウ)(エ)

x=2,3,4,5,y=4,5で考える。

x^2を5で割って余る値は0,1,4。y^2を5で割って余る値は0,1。

これを組み合わせて0,1,2,4の4つ。

(オ)

6583^5=(6580+3)^5　これを5で割った余りは、二項定理より3^5。

3^5=243でこれを5で割って余りは3。

(カ)

2(x^2+y^2)が共通の余りを持つ時x^2+y^2の余りが4である必要がある。

この時の(Ｘ,Ｙ)の組は(Ｘ,Ｙ)=①(0,2)②(0,3)③(2,0)④(3,0)のみで

①の場合　2≦5m≦100 4≦5n+2≦102から　1≦m≦20　1≦n≦20から20^2通り。

②の場合 1≦m≦20 4≦5n+3≦102から　1≦n≦19から　20×19通り。

③の場合　4≦5n≦102 2≦5m+2≦100から　1≦n≦20　1≦m≦19から20×19通り。

④の場合　1≦n≦20 2≦5m+3≦100から 0≦m≦19から　20^2通り。

よって、20(20×2+19×2)=20×78=1560通り　

NO.7-4　余り

問題

301 ：以下、名無しにかわりましてVIPがお送りします：2009/02/19(木) 23:58:45.88 ID:8hPvdPD20
   120以下の自然数のうち、その数を2乗して120で割ったあまりが1であるような自然数はいくつあるか？ 

予想解答

...

12個

予想解説

ある数をnとおく(n=1～120)

n^2=120k+1 (0≦k≦119)

(n+1)(n-1)=120k

右辺偶数より左辺偶数よりnは奇数。

n=2m+1とおいて(m=0～59)

(m+1)m=30k

(m+1)m/2=15k(連続二数の積は必ず偶数)

m+1=5sかつm=3t

m+1=15s(それぞれ逆を含む)

このように考えると

(1)m+1=5sかつm=3t 5s-1=3t これはs=2+3jで成立する。

m+1=5s=5(2+3j)

m=5(2+3j)-1

1≦10+15j≦60

0≦j≦3で4通り。(m=9,24,39,54からn=19,49,79,109)

(2)m+1=3sかつm=5t

3s=5t+1

これはt=1+3jで成立する。

m=5(1+3j)

0≦5(1+3j)≦59

• 5≦15j≦54

∴j=0,1,2,3で4通り(m=5,20,35,50からn=11,41,71,101)

(3)m+1=15s

0≦15s-1≦59

∴s=1,2,3,4で4通り(m=14,29,44,59からn=29,59,89,119)

(4)m=15t

0≦15t≦59

∴t=0,1,2,3で4通り(m=0,15,30,45からn=1,31,61,91)

よってn=1,11,19,29,31,41,49,59,61,71,79,89,91,101,109,119

NO.7-5　お金～難易度☆☆★★★

問題

25 ：以下、名無しにかわりましてVIPがお送りします：2009/04/05(日) 21:02:02.51 ID:1SfWRF9LO
   やる夫が1個61円の品物Aと1個92円の品物Bと1個123円の品物Cをそれぞれいくつかずつ買ったところ、合計金額が4000円になった。
   (問)やる夫は合計でいくつの品物を買ったか。

解答

...

61個

解説

4000=61A+92B+123Cとしてこれを満たすA,B,Cを求める。

ここで、61 92 123は等差数列をみたしていることを頭にとどめておこう。

そこで、以下のように変形する

4000=(92-31)A+92B+(92+31)C=92(A+B+C)+31(C-A)

A+B+C=P,C-A=Q(P>Q)とでもおくと4000=92P+31Q

4000=(31*3-1)P+31Q=31(3P+Q)-P

4000=31*131-61よりP=61,Q=-52とすれば成立。また他の場合で成立しないことは

4000=31*130-30からP=30,Q=40とするとQ>Pで不適。以下も同様。

4000=31*132-92よりP=92,Q=-144となるがこの時A>144からP>144で不適。

それ以上それ以下においてはさらに条件が厳しくなるため不適。

∴P=A+B+C=61

なんかの倍数と余りという形になんとか変形していきたいところ。

NO.7-6　対称性と必要条件

問題(画像省略)

1 ： ◆zYSTXAtBqk ：2009/04/16(木) 14:57:56.53 ID:7Awri16l0
   三つの自然数a,b,cがある。
   abをcでわると1余り
   bcをaでわると1余り
   caをbでわると1余る。
   このような三つの自然数の組(a,b,c)を決定しなさい。
   答えをトリップ
   a+b+c=kとして名前欄に #k と入力

解答

...

(a,b,c)=(2,3,5),(2,5,3),(3,2,5),(3,5,2),(5,2,3),(5,3,2) (a+b+c=10)

解説

ab+bc+caを考えるとa,b,cのいずれで割っても1余るから

ab+bc+ca-1はabcの倍数。

∴ab+bc+ca-1=kabc(kは自然数)として表せる。

a,b,c≠0よりabcで両辺割って

1/a+1/b+1/c=k+1/abc

実は、ここでNO.7-1の問題に近い形に帰着されました。

a≦b≦cとすると

k+1/abc≦3/a≦3であるから、k＜3なのでk=1,2である。

(ⅰ)k=1の時

a≧3の時 1/a+1/b+1/c≦1/3*3=1だが、1+1/abc＞1で不適。

よって、a=2かa=1でa=1の時は

1/b+1/c=1/bcからb+c=1だがこれを満たす自然数(b,c)の組は存在しない。

次にa=2の時は、

1/b+1/c=1/2+1/2bcから2b+2c=bc+1を得て(b-2)(c-2)=3。これを満たす自然数(b,c)は(3,5)。これは、題意に見合う。

(ⅱ)k=2の時

a≧3の時について、(ⅰ)と同様にして不適。

a=1の時は、1/b+1/c=1+1/bcからb+c=bc+1と変形され、(b-1)(c-1)=0からb=c=1。ただし、(1,1,1)は題意を満たさない。

a=2の時は、1/b+1/c=3/2+1/2bcから6b+6c=9bc+3と変形され、(3b-2)(3c-2)=1と変形されるが、b,c≧2よりこの式を満たす自然数(b,c)はない。

∴(a,b,c)=(2,3,5)に限る。(ただし、(a,b,c)の数を入れ替えたものも成立する。)

• 補足 なぜ、無駄な解が出てくるのかについてですがこの解法は必要条件を使って攻めているからです。

abをcでわると1余り、bcをaでわると1余り、caをbでわると1余る。⇒ab+bc+ca-1はabcの倍数は成立しますが、逆は成り立ちません。

反例は、丁度上の不適な解です。

NO.7-7　n次の時の余り ～難易度☆☆★★★

問題

48:以下、名無しにかわりましてVIPがお送りします :2009/07/20(月) 01:02:58.74 ID:MAjApoqj0
>>41 
複素数平面といえばこの問題かねｗ 
ｆ（ｘ）=ｘ＾2ｎ+ｘ＾ｎ+1　ｎは自然数 
ｘ＾2-ｘ+1で割り切れる条件は？ 
レベル　4おっぱい

解答

...

n=6k-4(kは自然数)

解説

x^2-x+1=0の解は

x=(1+-i√3)/2だからこれらをα,βとおく。

すると

f(x)=x^2n+x^n+1=(x-α)(x-β)Q(x)

これより

①f(α)=α^2n+α^n+1=0

②f(β)=β^2n+β^n+1=0を満たせばよい。

ただ、αとβは共役複素数であるから①と②は同値なので①だけを考える。

さてここで、α,β虚数立方根に近いことに着目して

α=(1-i√3)/2について考えると

α^2=(1-2i√3-3)/4=(-1-i√3)/2より

α^3=(-3-1)/4=-1だから

α^6=1なのでα^nは6の倍数で循環する。

α=(1-i√3)/2
α^2=(-1-i√3)/2
α^3=-1
α^4=(-1+i√3)/2
α^5=(1+i√3)/2
α^6=1

α^2m+α^n+1=0となる2m,nの組合わせは、mod6で考えて

2m≡2,n≡4または2m≡4,n≡2のみ。

よって、n≡2,n^2≡4かn≡4,n^2≡2を満たすnを考える。

n≡2⇒n^2≡4は必ず成立する。

n≡4⇒n^2≡4だからこの時n^2≡2にならず不適。

よって、n≡2の時

つまり、n=6k-4(kは自然数)で成立。