number theory

數學神童

puangenlun

if gcd(a,m)=1
then exist p and q such that
pa+qm=1
so pba+qbm=b
and pba=b-qbm
let x=pb
then ax=b mod(m)

數學神童

who can teach me part ii)??

數學神童

solve each of the congruences x^3=2(mod3) and x^3=2(mod5).Deduce the set of positive integers which satisfy both the congruences.
Hence,find the positive integers x and y which satisfy the equation
                                x^3+15xy=12152

puangenlun

solve each of the congruences x^3=2(mod3) and x^3=2(mod5).Deduce the set of positive integers which  ...
數學神童 发表于 31-10-2010 09:51 AM

x^3=2mod3

x^3=2mod5
[size=15.8333px]

[size=15.8333px]

[size=15.8333px]

[size=15.8333px]so x^3=2mod15
[size=15.8333px]

[size=15.8333px]

[size=15.8333px]

[size=15.8333px]x^3=15p+2

因此x^3的个位数只能是2或7

[size=15.8333px]所以x的个位数只能是3或8


[size=15.8333px]不妨设
[size=15.8333px]x=15p+3
[size=15.8333px]x=15p+8

但是当x=15p+3时不符合[size=15.8333px]x^3=2mod3


[size=15.8333px]因此[size=15.8333px]x=15p+8


[size=15.8333px]验证8^3=2mod15
因此(15p+8)^3=2mod15

设另有解y=15p+q,q<>8,0<=q<14
验算得y^3<>2mod15

故x=15p+8是通解。



---------------------------------------------------------



x^3+15xy=12152
x^3=12152-15xy

x^3=2mod3
x^3=2mod5

so x=15p+8

[size=15.8333px]x^3+15xy=12152
[size=15.8333px]x(x^2+15y)=12152


[size=15.8333px]代入x=8,23,38,........


得到x(x^2+15y)=8*1519=98*124=248*49=................

因为x,y>0,所以得到唯一解x=8,y=97




答案可能不完善（有欠考虑）。

puangenlun

最上面（B）

ax+by=k mod n
cx+dy=l mod n

acx+bcy=ck mod n
acx+ady=al mod n

=>(bc-ad)y=(ck-al) mod n

from (A)

if GCD(bc-ad,n)=1
then exists y such that
(bc-ad)y=k mod n
for any integer k

so y=(ck-al)(bd-ad)^(-1)

so x=..........................

puangenlun

29y=9 mod 16
y=11*29^(-1)=11*5=7 mod 16

7x=5
x=5*7^(-1)=5*7=3 mod 16

x=3 mod 16
y=7 mod 16

whyyie

Let n be an element of natural number and n is greater than or equal to 2,
(i) If n = 6k+1 or n =6k+5, with k is integer, prove that 2^n + n^2 =0 (mod 3).
(ii) If 2^n + n^2 is prime number, prove that n= 3 (mod 6)

yw46

(i) If n = 6k+1 or n =6k+5, with k is integer, prove that 2^n + n^2 =0 (mod 3).

6k + 1 = odd; 6k + 5 = odd
6k + 1 = 1mod3, 6k + 5 = 2mod3
n = ±1mod3 (odd)

2^n + n^2 = (-1mod3)^(odd) + (±1mod3)^2 = - 1 + 1 = 0mod3

(ii) If 2^n + n^2 is prime number, prove that n= 3 (mod 6)

n ≥ 2, 2^n + n^2  ≥ 8, so 2^n + n^2 = odd
2^n always even, so n = odd
since n is odd, it can only be 1/3/5 mod 6
but when n = 1 or 5 mod 6, 2^n + n^2 = 0 mod 3 (not prime)
so when 2^n + n^2 = prime, n = 3 mod 6

whyyie

yw46

x = r mod q >>> x^n = r^n mod q

19^n = 3^n mod 8
39^n = (-1)^n mod 8

when n is odd, 19^n + 39^n = 3 - 1 mod 8 = 2 mod 8
when n is even, 19^n + 39^n = 1 + 1 mod 8 = 2 mod 8