C5-8

Question 1

with a, b and d being natural numbers what is the equation in relation to d | a and d | b

Answer 1

d=as + bt

for integers s and t

Question 2

what is the greatest common divisor

Answer 2

natural number d satisfying the equation d=as + bt

Question 3

when is something said to be relatively prime (or coprime)

Answer 3

when it is true that two natural numbers (example) a and b have gcd(a,b) = 1

Question 4

Let a, b and c be integers that are relatively prime with a and b. What can be assumed

Answer 4

if a | bc then a | c
and
if a | c and b | c then ab | c

Question 5

write this as an equation: every positive integer n greater than 1 may be written…

Answer 5

n= p1 p2..pr where p is a prime number and r is greater than or equal to 1.

Question 6

what is the lowest common multiple

Answer 6

the smallest positive integer that is divisible by both a and b

Question 7

how do you use the efficient method for finding the gcd

Answer 7

Euclidean algorithm

when a and b are natural numbers
if b= aq+r where q and r are positive integers, then gcd (b,a)= gcd (a,r)

Question 8

what is the Diophantine equation

Answer 8

ax + by = c

which only has a solution if d | c where d= gcd (a,b)

Question 9

what is the formula when something is congruent to a modulus

Answer 9

letting n > 1 as a fixed positive integer called modulus. We say two integers a and b are congruent modulo n and write
a ≡ b (mod n)

Question 10

a (mod n) ≡ ?

Answer 10

a

Question 11

if a ≡ b (mod n)

Answer 11

then b ≡ a (mod n)

Question 12

if a ≡ b (mod n) and b≡ c (mod n)

Answer 12

then a ≡ c (mod n)

Question 13

if a ≡ b (mod n) and c ≡ d (mod n)

Answer 13

then a + c ≡ b + d (mod n)
and
ac ≡ bd (mod n)

Question 14

(5) if a ≡ b (mod n)

Answer 14

then a + c ≡ b + c (mod n)
and
ac ≡ bc (mod n)

Question 15

(6) if a ≡ b (mod n)

Answer 15

then a^k ≡ b^k (mod n) for any positive integer k

Question 16

if ac ≡ bc (mod n) and gcd (c, n) =1

Answer 16

then a ≡ b (mod n)

Question 17

what is the equation for congruence classes

Answer 17

[a] (sub)n = {bEZ : b ≡ a (mod n)}

Question 18

define the sum of congruence classes

Answer 18

where they all have (sub) n outside the bracket representing (mod n)

[a] + [b] = [a+b]

Question 19

define the product of congruence classes

Answer 19

where they all have (sub) n outside the bracket representing (mod n)

[a] [b] = [ab]

Question 20

what is the equation when [a]n is invertible

Answer 20

[a]n [b]n = [1]n

Question 21

what equation shows the linear congruence

Answer 21

ax ≡ b (mod n)

Question 22

how to solve a linear congruence

Answer 22

calculate d= gcd (a,n)

test whether d divides b, if it doesn’t then no solutions exist

if d | b then there are d solutions in Zn
(a/d)x ≡ b/d (mod n/d)

since gcd (a/d, n/d) = 1 there is one solution to Zn/d

find inverse of [a/d] n/d (sub) and calculate
(all with mod n/d)
[x] = [inverse] [b/d]

from [x] obtain a specific solution