CS701_Assignment_No.1_2017 Theory of Computation

[WAQAR ABBASI]

NEED HELP IN CS701 ASSIGNMENT NO.1

DUE DATE 09-11-2017

[Adeel]

Nothing uploaded yet
Question No 2 required
if some solve,
then
upload it

[Zaheer Abbas]

The given equation 33x + 15y = 14 has no integral solutions.

I’d prove a more generic and stronger claim.

Claim : The equation ax+by=c
has integers if and only if gcd(a,b)|c.

Observe that it works both ways.

Proof :

For the forward direction.

Given ax+by=c
has integer solution. To prove gcd(a,b)|c.

Assume gcd(a,b)=k.

∴a=kq

∴b=kr

for some q,r∈I

∴kqx+kry=c

∴k(qx+ry)=c

∴k|c⇒gcd(a,b)|c.

Hence the forward direction proof is complete.

For the reverse direction.

Given gcd(a,b)|c.
To prove ax+by=c

has integer solution.

Since k
is the gcd(a,b) there exist integers x′,y′∈Z such that ax′+by′=k.

Also, k|c⇒c=kd
for some integer d.

∴ax′+by′=k

∴d(ax′+by′)=kd

∴a(dx′)+b(dy′)=c

Implies that ax+by=c

has integer solution.

This proves our claim.

for given equation, gcd(15,33)=3∤14.
Hence no integer solution.

[Adeel]

what about question no 2

[dolldoll]

hav u solved sereach paper question?

[Mah hoor]

how can run jflap

[+ M.Tariq Malik]

Dear Students Don’t wait for solution post your problems here and discuss ... after discussion a perfect solution will come in a result. So, Start it now, replies here give your comments according to your knowledge and understandings....

[+ M.Tariq Malik]

Question No 2

CS701 Assignment Qustion No 1 Solution
Sol.
Ax+By=C
Coefficient ko comapre karain with given equation 33x+15y=14

A=33
B=15
C=14
The greatest common factor (GCR) of A and B must be divisible by C
GCF of A and B is 3
33/3=11
And
15/3=5

But this 3 is not not divisible by 14
As
14/3===not divisible
hence the given statement has no integer solution

[+ M.Tariq Malik]

check video also