Ian Morrison - Cleveland State University



Ian Morrison

MTH 493

Homework 1

1. (1) Find the solution set (if it exists), and compute one pair of integers that satisfies the equation [pic].

First, solve the equation [pic].

The gcd(234,321) = 3 from GCD algorithm in python. So let[pic].

Use the XGCD algorithm in python to find [pic]and[pic]. So [pic] and [pic].

18 is divisible by[pic], so [pic] has infinitely many solutions.

Let [pic].

To find one solution, solve the equation [pic], where [pic]and [pic].

The solution to the equation [pic] is [pic] and [pic].

Plugging [pic] and[pic] into [pic] yields [pic], which is true.

1.(2) Find the solution set (if it exists), and compute one pair of integers that satisfies the equation [pic].

The gcd(25,49) = 1.

[pic] and [pic] is obvious by inspection.

The solution to the equation [pic] is [pic] and [pic].

1.(3) Find the solution set (if it exists), and compute one pair of integers that satisfies the equation [pic]

First, solve the equation [pic].

The gcd(385,84) = 7 from GCD algorithm in python. So let[pic].

10 is not divisible by 7, so the equation has no integer solutions.

2. (1) Find [pic], if it exists. [pic].

The inverse exists because 8 is relatively prime to 31.

To find the inverse, solve the equation [pic].

Using XGCD algorithm yields [pic].

So [pic].

Check answer: [pic].

2.(2) Find [pic], if it exists. [pic].

The inverse does not exist because gcd(18,30) = 6.

2.(3) Find [pic], if it exists. [pic].

The inverse exists because 2 is relatively prime to 51.

To find the inverse, solve the equation [pic].

Using XGCD algorithm yields [pic].

So [pic].

Check answer: [pic].

[pic]

3.(1) Find all solutions of [pic]

Looking at the diagonal rows of the table shows that the solutions are [pic] and [pic].

3.(2) Find all solutions of [pic]

Looking at the diagonal rows of the table shows that there are no solutions.

3.(3) Find all solutions of [pic].

This is equivalent to [pic], which is congruent to [pic].

First inspect the diagonal row of the squares which contains only [0],[1],[4], and [7].

The only possible candidates for solutions are {[1],[4],[7]}, because [pic]is obviously not a solution.

[pic]is an obvious solution because [pic].

[pic]is a solution because [pic]by the table and [pic].

Likewise, [pic]is a solution because [pic]by the table and [pic].

So the solution set to the equation [pic] is [pic],[pic], and[pic].

4.(1) Calculate [pic]

Use the formula[pic]where[pic]are the prime factors of [pic].

The prime factors of 12 are 2 and 3.

So [pic]=[pic]

4.(2) Calculate [pic]

The prime factors of 144 are 2 and 3.

So [pic]=[pic]

5. Use Euler’s theorem to compute [pic].

According to Euler’s theorem, [pic] if [pic]

Gcd(5,847) = 1 obvious because 5 is prime and 847 not a multiple of 5.

In this case, [pic] and [pic](obtained by trial factorization and [pic] formula)

[pic].

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download