is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

You will get a detailed answer to your question or assignment in the shortest time possible.

## Here's the Solution to this Question

1. a)

There is an integer $k$ such that $ak=b$

Then:

$bc=akc$

So: $a|bc$

b) There are integers $k$ and $m$ such that:

$ak=b,bm=c$

Then:

$akm=c$

So: $a|c$

2.a)

 # Simple python code that first calls pow()
# then applies % operator.
a = 2
b = 100
p = (int)(1e9+7)

# pow function used with %
d = pow(a, b) % p
print (d)

Output: $976371285$

b)

# Python algorithm compute all primes smaller than or equal to
# n using Sieve of Eratosthenes

def SieveOfEratosthenes(n):

# Create a boolean array "prime[0..n]" and initialize
# all entries it as true. A value in prime[i] will
# finally be false if i is Not a prime, else true.
prime = [True for i in range(n + 1)]
p = 2
while (p * p <= n):

# If prime[p] is not changed, then it is a prime
if (prime[p] == True):

# Update all multiples of p
for i in range(p * 2, n + 1, p):
prime[i] = False
p += 1
prime[0]= False
prime[1]= False
# Print all prime numbers
for p in range(n + 1):
if prime[p]:
print p, #Use print(p) for python 3


3.Euclidean Algorithm to compute the greatest common divisor.

from math import *

def euclid_algo(x, y, verbose=True):
if x < y: # We want x >= y
return euclid_algo(y, x, verbose)
print()
while y != 0:
if verbose: print('%s = %s * %s + %s' % (x, floor(x/y), y, x % y))
(x, y) = (y, x % y)

if verbose: print('gcd is %s' % x)
return x

4.

 # function for extended Euclidean Algorithm
def gcdExtended(a, b):
# Base Case
if a == 0 :
return b,0,1

gcd,x1,y1 = gcdExtended(b%a, a)

# Update x and y using results of recursive
# call
x = y1 - (b//a) * x1
y = x1

return gcd,x,y

5.

$a=299,b=117$

$a=bq+r$

$299=2\cdot117+65$

$117=65\cdot1+52$

$65=52\cdot1+13$

$52=13\cdot4+0$

$gcd=13$

6.If $m=gcd(1002,71)$

$1002=71\cdot14+8$

$71=8\cdot8+7$

$8=7\cdot1+1$

$7=1\cdot7+0$

$gcd=1$

Then:

$1=8-1\cdot7=8-1\cdot(71-8\cdot8)=-1\cdot71+8\cdot9=$

$=-1\cdot71+9\cdot(1002-71\cdot14)=9\cdot1002-15\cdot71$

$p=9,q=-15$

7.

$486=2\cdot222+42$

$222=42\cdot5+12$

$42=12\cdot3+6$

$12=6\cdot2+0$

$gcd=6$

$6=42-12\cdot3=42-3(222-42\cdot5)=-3\cdot222+16\cdot42=$

$=-3\cdot222+16(486-2\cdot222)=16\cdot486-35\cdot222$

$x=16,y=35$

8.

$421=38\cdot11+3$

$11=3\cdot3+2$

$3=2\cdot1+1$

$2=1\cdot2+0$

$gcd=1$

$1=3-1\cdot2=3-(11-3\cdot3)=-11+3\cdot4=-11+4(421-38\cdot11)=$

$=4\cdot421-39\cdot11$

$x=4,y=153$