from numpy import divide
print 'Division Algorithm'
a=4461# #dividend
b=16# #divisor
r=(a%b) #remainder
k=divide(a,b) #quotient
j=b*k+r #dividend=divisor*quotient+remainder
a=-262# #dividend
b=3# #divisor
k=divide(a,b) #remainder
r=(a%b) #quotient
j=b*k+r #dividend=divisor*quotient+remainder
print 'a and j have equal values.Hence division algorithm is proved'
from math import floor
print 'Divisibility and Primes'
x=50#
print 'prime numbers less than 50 are'
def get_primes(n):
numbers = set(range(n, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return primes
y=get_primes(x)
print 'the prime factorisation of 21,24 and 1729 respectively are:'
def factors(n):
primfac = []
d = 2
while d*d <= n:
while (n % d) == 0:
primfac.append(d) # supposing you want multiple factors repeated
n //= d
d += 1
if n > 1:
primfac.append(n)
return primfac
k=factors(21)
l=factors(24)
n=factors(1729)
print k,l,n
from numpy import int32
import numpy as np
print 'the GCD of the following numbers is:'
def gcd(a, b):
a, b = np.broadcast_arrays(a, b)
a = a.copy()
b = b.copy()
pos = np.nonzero(b)[0]
while len(pos) > 0:
b2 = b[pos]
a[pos], b[pos] = b2, a[pos] % b2
pos = pos[b[pos]!=0]
return abs(a)
print "gcd(12,18) = ",gcd([12],[18])
print "gcd(12,-18) = ",gcd([12],[-18])
print "gcd(12,-16) = ",gcd([12],[-16])
print "gcd(29,15) = ",gcd([29],[15])
print "gcd(14,49) = ",gcd([14],[49])
from numpy import floor
print 'Euclidean Algorithm'
a=[540,168,36,24]#
b=[168,36,24,12]#
thegcd=[]
for i in range(0,4):
thegcd.append(gcd(a,b))
def myf(dividend,divisor):
quotient=floor(dividend/divisor)#
rem=(dividend%divisor)#
k=quotient*divisor+rem#
print k
if(rem!=0):
myf(divisor,rem)
myf(540,168)
print 'for the equation 540*x+168*y=12,we are given'
a=540#
b=168#
c=24#
d=36#
d=a-3*b# #Eqn (1)
c=b-4*d# #Eqn (2)
k=d-1*c# #Eqn (3)
5*d-1*b# #Eqn (4)
k=d-b+4*d# #substituting value of c in Eqn (3) from Eqn (2)
r=5*a-16*b#
if(r==k):
print 'x=5 and y=16'#
a=2**4*3**3*7*11*13
b=2**3*3**2*5**2*11*17
d=gcd([a],[b])
print "gcd(a,b) =",d
lcm1=2**4*3**3*5**2*7*11*13*17 #lcm is the product of those primes which appear in either a or b
print "lcm(a,b) =",lcm1
print 'solving for the congruence equation 8x @ 12(mod 28) ,where @ is the sign for congruence'
a=8#
b=12#
m=28#
d= gcd([a],[m])#
a1= a/d#
b1= b/d#
m1= m/d#
def f(x):
yd= (a1*x)-b1
return yd
print 'k is the unique solution of the equation '
for i in range(0,m1):
x=i#
p=f(x)#
if((p%m1) == 0):
k=x
break#
s1=[k]#
s2=k+m1#
s3=k+(m1*2)#
s4=k+(m1*3)#
print 'solutions of the original equation at d=4'
print s1
print s2
print s3
print s4