Компютърна Алгебра

[Silvanich]

Здравейте! Не знам дали съм улучила правилния форум и раздел, но имам едно домашно, с което не мога да се справя сама. Почти нищо не разбирам от тези задачи и ако имате възможност да ми помогнете, ще ви бъда много благодарна. Ето това са задачите

1.) Докажете, че ако d=gcd(a,b) и d=ax+by , то gcd(x,y)=1.

2.) Редицата на Фибоначи се определя от равенствата:
[tex]f_{0}=f_{1}=1 , f_{n+2}=f_{n+1}+f_{n} , n\ge0[/tex]

Намерете [tex]gcd (f_{n+1}, f_{n})[/tex]

3.) Решете сравненията:
а)
[tex]x\equiv 1(mod2) [/tex]
[tex]x\equiv 2(mod5) [/tex]
[tex]x\equiv 5(mod7) [/tex]

б)
[tex]x\equiv 5(mod13) [/tex]
[tex]x\equiv 2(mod17) [/tex]
[tex]x\equiv 6(mod9) [/tex]
[tex]x\equiv 4(mod7) [/tex]

в)
[tex]x\equiv 24(mod13) [/tex]
[tex]x\equiv 52(mod17) [/tex]
[tex]x\equiv -1(mod19) [/tex]

4.) Напишете програма (алгоритъм) MODINV, която при зададено цяло число [tex]a[/tex] и естествено число [tex]n[/tex] проверява дали двете числа са взаимно прости и ако са, намира естественото число [tex]x[/tex] такова, че [tex]ax\equiv 1(modn)[/tex]. Изпълнете програмата за следните входни данни:
[tex]a=225, n=33;[/tex]
[tex]a=225, n=11; [/tex]
[tex]a=3,n=344;[/tex]
[tex]a=2,n=315.[/tex]

5.) Напишете програма GLE(General Linear Equetion), която по зададени цели числа [tex]a,b,c, a^{2}+b^{2}\ne 0[/tex] , връща цели числа [tex]x,y,t[/tex], където:

t=0, ако [tex]ax+bx=c[/tex] има решение в цели числа;
t=1, ако уравнението няма решение в цели числа.

Ако t=1, се изпицва "У-то няма реш. в цели числа.". Изпълнете програмата за следн. вх. данни:
[tex]168x-66y=42;[/tex]
[tex]343x+407y=7;[/tex]
[tex]426x-156y=128;[/tex]
[tex]1463x+4235y=11[/tex].

[Реклама]

[Fed]

1. Докажете, че ако d=gcd(a,b) и d=ax+by , то gcd(x,y)=1.
Само ще подскажа: допусни, че gcd(x,y)≠1, тогава x = d₁.x₁, y = d₁y₁, d₁ ≠ 1 ...

2. (f_n+1, f_n) = (f_n-1 + f_n, f_n-1 + f_n-2) = (f_n-1 + f_n-2, f_n-1) = ... = (f₂ + f₁, f₁) = (f₁ + f₀, f₀) = (2,1) = 1.

за другите ме мързи...

[Silvanich]

Аз за втората всъшност го бях намерила това, но все пак мерси..
Сега ще се опитам да реша някоя, макар че нищо не разбирам