初等数论讨论中心

hamilan911

原帖由 dunwan2tellu 于 9-2-2006 03:38 PM 发表
题目：组合数论

对于所有的正整数，若号码从左到右一直在增加，我们就称他为“幸运数”。请问在正整数集合里总共有几个“幸运数”呢？Ex：２３８９是幸运数。３２８９不是。

已知123456789是最大的“幸运数”。
而12，13，123，124，1235，2346，12345,...,12345678,12345679等等都是幸运数。。。
要形成幸运数就类似于从“123456789”中抽出0个，1个，2个，3个,...，8个数。
也就是9C0+9C1+9C2+9C3...+9C7+9C8
(1+x)^9 = 1 + 9C1 x + 9C2 x^2 + 9C3 x^3 + ...9C9 x^9
x=1
2^9 = 1 + 9C1 + 9C2 + 9C3 + ...9C9
9C0 = 9C9
所以9C0+9C1+9C2+9C3...+9C7+9C8 = 2^9 - 1 = 511

dunwan2tellu

题目：

2^10 + 5^12 是否是质数(prime)？

hamilan911

原帖由 dunwan2tellu 于 20-2-2006 04:57 PM 发表
题目：

2^10 + 5^12 是否是质数(prime)？

2^10 + 5^12 = (2^5 + 5^6)^2 - 2*2^5*5^6
            = (2^5 + 5^6)^2 - (10^3)^2
            = (2^5 + 5^6 + 10^3)(2^5 + 5^6 - 10^3)
所以2^10 + 5^12 不是质数。

dunwan2tellu

原帖由 hamilan911 于 20-2-2006 05:18 PM 发表


2^10 + 5^12 = (2^5 + 5^6)^2 - 2*2^5*5^6
            = (2^5 + 5^6)^2 - (10^3)^2
            = (2^5 + 5^6 + 10^3)(2^5 + 5^6 - 10^3)
所以2^10 + 5^12 不是质数。

花了21分钟就做到了。呵呵！不错！其实就是分解
a^4 + 4b^4 = (a^2+2b^2+2ab)(a^2+2b^2-2ab)

dunwan2tellu

题目：完全平方数

请问 111...11222..2225 (共有 2005 个“ 1” 和 2006 个 “2”) 是不是完全平方数(perfect suqare)？

hamilan911

已知(10a+5)(10a+5)=100a^2 + 100a + 25
而111...11222..2225 (共有 2005 个“ 1” 和 2006 个 “2”) 的末位数也是二十五，所以只需证明111...11222..2200 (共有 2005 个“ 1” 和 2005 个 “2”)是100a(a+1),就可看出是个平方数。。。
111...22200=111...222*100
设11...11(2005个1）= X
所以11...1122...22 = 10^2005 X + 2X = (10^2005 + 2)X
由于10^2005 + 2 的每个位数的和是3，所以能被三整除。
10^2005 + 2 = 99...99(2005个9）+ 3
            = 33...33(2005个3）*3 + 3
            = 3*（33...33(2005个3）+ 1）
11...1122...2200 = 3*（33...33(2005个3）+ 1）*11...11(2005个1)*100
                 = (3*11...11(2005个1))（33...33(2005个3）+ 1）*100
                 = a(a+1)*100
11...1122...2225 = (10a+5)^2
所以这数目是个平方数。。
dunwan2tellu,我觉得这解法有点麻烦，你有更简单的吗?

[ 本帖最后由 hamilan911 于 21-2-2006 05:34 PM 编辑 ]

dunwan2tellu

原帖由 hamilan911 于 21-2-2006 05:30 PM 发表
已知(10a+5)(10a+5)=100a^2 + 100a + 25
而111...11222..2225 (共有 2005 个“ 1” 和 2006 个 “2”) 的末位数也是二十五，所以只需证明111...11222..2200 (共有 2005 个“ 1” 和 2005 个 “2”)是100a(a+1),就 ...

你的方法挺不错的！我都没想到能这样变！

我的做法如下：

设 x = 11...11 (2005个1) 则

11..1122..225 = 10^2007*x + 200x + 25

之后用 x = 1/9 * (10^2005 - 1) ==> 9x+1=10^2005 . 所以 10^2007 = 100(9x+1) .因此得到

100x(9x+1)+200x+25 = (30x+5)^2

dunwan2tellu

题目：整数解
请找出所有a,b,c的自然数解。

a^2 + b^2 + c^2 = (ab)^2

hamilan911

(ab)^2 - a^2 - b^2 + 1 = 1 + c^2
(a^2 - 1)(b^2 - 1) = 1 + c^2
已知for任何x,
x = m^p* n^q*o^r...    m,n,o都是质数
所以 1 + c^2 = m^p*n^q*o^r...
而 (a^2 - 1)和(b^2 - 1) 都不是大过三的质数或质数的任何方
当a = 2, a^2 - 1 = 3
可是 c^2 + 1 = 1,2(mod 3)  (冲突）
当a = 1, a^2 - 1 = 0  -->(a^2 - 1)(b^2 - 1) = 0  
但 1+c^2 > 0 （冲突）
所以 a = 0
b^2 + c^2 = 0
b=0,c=0

0不是自然数，所以a,b,c无解。

[ 本帖最后由 hamilan911 于 27-2-2006 10:00 PM 编辑 ]

原帖由 hamilan911 于 21-2-2006 05:30 PM 发表
已知(10a+5)(10a+5)=100a^2 + 100a + 25
而111...11222..2225 (共有 2005 个“ 1” 和 2006 个 “2”) 的末位数也是二十五，所以只需证明111...11222..2200 (共有 2005 个“ 1” 和 2005 个 “2”)是100a(a+1),就 ...

另一种方法

hamilan 经已完成至
a^2+a=111...111222...222(2005个1,2005个2）
a(a+1)=111...111222...222

111*1111=123321
1111*11111=12344321
11111*1111111234554321

所以...
let x=11..111(2005个1）
111...111222...222(2005个1,2005个2
=   x(10x+1)      +         10x[(x-1)/10]          +     x
123...321(4010digit)     123...3210(4010digit)    111..111(2005digit)
a(a+1)=x(10x+1)+x(x-1)+x
a(a+1)=3x(3x+1）
compare LHS & RHS
a=3x

111...111222...22225(题目）=(10a+5）^2
                           =33..3335(2006digit)

dunwan2tellu

原帖由 伊利布利 于 23-2-2006 06:28 PM 发表


另一种方法

hamilan 经已完成至
a^2+a=111...111222...222(2005个1,2005个2）
a(a+1)=111...111222...222

111*1111=123321
1111*11111=12344321
11111*1111111234554321

所以...
let x=11..111 ...

呵呵！终于肯贴上来了！能注意到这特点还真不简单！却有千呼万唤始出来，犹见琵琶半遮面的感觉...

不过有些typing error , 应该是  
x(10x+1)  -  10(x(x-1)/10)  +  x
4010 digit   4009 digit       2005 digit



[ 本帖最后由 dunwan2tellu 于 23-2-2006 07:02 PM 编辑 ]

dunwan2tellu

质因子：
若 n = p1^(a1)p2^(a2)...pn^(an)  , p1<p2<...<pn 则 n 的因子共有 (a1+1)(a2+1)...(an+1) 个。
Ex : 20 = 2^2 x 5^1 所以共有 (2+1)(1+1)=6 个因子。i.e : 1,2,4,5,10,20

题目：
(i)请问 800 有多少个因子（factor)? Ex : 2,4,50,200 都是800的factor

(ii) 证明为何因子共有 (a1+1)(a2+1)...(an+1) 个。

[ 本帖最后由 dunwan2tellu 于 3-3-2006 04:29 PM 编辑 ]

dunwan2tellu

Wilson Theorem :

多于任何质数 p ,必有

(p-1)! == -1 (mod p)  

Ex : p = 5 -->  (5-1)!== 24 == -1 (mod 5)

题目：
求 2000！被 2003 除后的余数。

hamilan911

(i)800 = 5^2 x 2^5
所以共有(2+1)(5+1) = 18个因子

(ii)若 n = p1^(a1)p2^(a2)...pn^(an)
    p1^0,p1^1,...p1^(a1)会是n的因子，所以共有（a1+1)C1个因子。。。
    p2^0,p2^1,...p2^(a2)会是n的因子, 所以共有（a2+1)C1个因子。。。
    因子的总数 =（a1+1)(a2+1)(a3+1)...(an+1)

[ 本帖最后由 hamilan911 于 3-3-2006 08:50 PM 编辑 ]

hamilan911

原帖由 dunwan2tellu 于 3-3-2006 04:25 PM 发表
Wilson Theorem :

多于任何质数 p ,必有

(p-1)! == -1 (mod p)  

Ex : p = 5 -->  (5-1)!== 24 == -1 (mod 5)

题目：
求 2000！被 2003 除后的余数。

2002! == -1(mod 2003)  -(1)
2002  == -1(mod 2003)  -(2)
从(1)和(2),2001! ==  1 == 2004(mod 2003)  -(3)
2001  == -2(mod 2003)  -(4)
从(3)和(4), 2000! == -1002 == 1001(mod 2003)
2000!被 2003 除后的余数是1001.

hamilan911

来一题简单的，证明连续三个奇数一定会有至少两个互素。

dunwan2tellu

原帖由 hamilan911 于 4-3-2006 03:35 PM 发表
来一题简单的，证明连续三个奇数一定会有至少两个互素。

上面的都答对了！

对于你的题目，我觉得是两两互素。

设他们为 2k+1,2k+3,2k+5 , 由于 2k+1,2k+3 只差 2,所以他们的common prime 只可能是 2,但是他们都是奇数，故没有commonprime . 同理,2k+3,2k+5 也没有 common prime ==> GCD (2k+1,2k+3)=(2k+3,2k+5)=1

其实也不难看出 (2k+1,2k+5)=1 ,因为他们差 4,所以common prime 只能是 2 ，3.不可能是 3,因为如果是的话，那么 2k+1和 2k+5必定要 一奇一偶，矛盾！


一个网友问的题目

设 x_i (i=1,2,3...,n) 为整数，且符合

(i)x_1 + x_2 + ... + x_n = 0
(ii) (x_1)(x_2)(x_3)...(x_n) = n

证明　ｎ　必为　４的倍数。

dunwan2tellu

找出所有x,y,z的自然数解，满足

7^x - 3^y = 4^z

dunwan2tellu

求自然数解例子：

求 2^x = 3^y + 7 的自然数解

解法：不难　看出 (x,y)=(4,2)是其解。我们将要证明这就是为一解。

设 x,y>= 3时有解。那么拿 mod 4 得到

0 == (-1)^y -1  (mod 4)  ==>  1 == (-1)^y (mod 4) .所以 y 必定是偶。

拿mod 3 得到

(-1)^x == 1 (mod 3) 所以 x 必定是偶。

设 x = 2m , y = 2n ( m,n都是整数)

那么 2^(2m) - 3^(2n) = 7 ==> (2^m -3^n)(2^m+3^n)=7

明显只有 2^m -3^n = 1 和 2^m + 3^n = 7 ==> m = 2 , n = 1 所以 (x,y)=(4,2)


*用大概同样的概念，来接上面的贴的题目吧！

hamilan911

原帖由 dunwan2tellu 于 6-3-2006 03:28 PM 发表
找出所有x,y,z的自然数解，满足

7^x - 3^y = 4^z

拿mod4,
(-1)^x - (-1)^y = 0
所以x,y必定是同奇同偶。。。
当z>1,拿mod8,
(-1)^x - 3^y = 0
+1或-1 - 3或1= 0
所以x,y同偶
7^2x' - 3^2y' = 4^z
(7^x' + 3^y')(7^x - 3^y')= 4^z
7^x' + 3^y' = 4^a
7^x' - 3^y' = 4^b
a+b = z
7^x = 1/2 * (4^a +4^b)
    = 2^(2a-1) + 2^(2b-1)
    = 2^(2a-1)(1 + 2^(2b - 2a))
a=0
所以 7^x' - 3^y' = 1
     7^x' + 3^y' = 4^z
7^x - 3^y = 1
拿mod 8, (-1)^x - 3^y = 1  无解
所以z>1 无解
7^x - 3^y = 4
显然（x,y) = (1,1)
因为当x>1,  7^x - 3^y > 4

[ 本帖最后由 hamilan911 于 11-3-2006 05:39 PM 编辑 ]