# Chapter11 - Properties of integers¶

## Ex11.2 Pg 319¶

In [1]:
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'

Division Algorithm
a and j have equal values.Hence division algorithm is proved


## Ex11.4 Pg 320¶

In [2]:
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

Divisibility and Primes
prime numbers less than 50 are
the prime factorisation of 21,24 and 1729 respectively are:
[3, 7] [2, 2, 2, 3] [7, 13, 19]


## Ex11.5 Pg 321¶

In [3]:
from numpy import int32
import numpy as np
print 'the GCD of the following numbers is:'
def gcd(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])

the GCD of the following numbers is:
gcd(12,18) =  [6]
gcd(12,-18) =  [6]
gcd(12,-16) =  [4]
gcd(29,15) =  [1]
gcd(14,49) =  [7]


## Ex11.6 Pg 322¶

In [4]:
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'#

Euclidean Algorithm
540.0
168.0
36.0
24.0
for the equation 540*x+168*y=12,we are given
x=5 and y=16


## Ex11.9 Pg 324¶

In [5]:
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

gcd(a,b) = [792]
lcm(a,b) = 183783600


## Ex11.19 Pg 332¶

In [7]:
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

solving for the congruence equation 8x @ 12(mod 28) ,where @ is the sign for congruence
k is the unique solution of the equation
solutions of the original equation at d=4
[5]
[12]
[19]
[26]