Question Given that a and x are integers, a > 1: a|(3x + 2) and a|(12x + 3), fin

Question

Question

Given that a and x are integers, a > 1: a|(3x + 2) and a|(12x + 3), find Suppose a and b are relatively prime integers and c is an integer such that a | c and b | c. Prove that ab | c [ You will need to use the definitions of "relatively prime" and "divides"]. Use the Euclidean Algorithm to nd the greatest common divisor of a = 1047 and b = 259 and express it in the form ma + nb for suitable integers m and n. Define f : N {1} rightarrow N by setting f (n) equal to the largest prime divisor of N Find the range of f. is f one-to-one? is f onto? Why did we not express f as a function N rightarrow N ? Explain your answers. This question concerns congruence mod 11. List 4 positive and 2 negative integers in 4- and in -4- . What is the general form of an integer in 4- and of an integer in -4- ? Find 242 (mod 15). List all congruence classes for congruence mod 6, giving the most usual and one other name for each. Use Fermat's Little Theorem to compute 3 502 : (mod 503), 3 503 (mod 503) and 3505 (mod 503).

Explanation / Answer

1) a divides [4*(3x+2) - (12x+3)] = 5 , a divides 5 , since a>1 a = 5;

2) a,b are relatively prime. So there exists integers x,y such that a*x + b*y = 1

a divides c -> c = a*m

b divides c -> c = b*n ( where m,n are integers)

a*x + b*y = 1

multiply both sides by c

c*a*x + c*b*y = c

b*n*a*x + a*m*b*y = c

ab ( n*x + m*y) = c

thus ab divides c

3) 1047 = 259*4 + 11

259 = 11*23 + 6

11 = 6* 1 + 5

6 = 5*1 + 1

5 = 1*5 + 0

gcd of 1047 , 259 is 1 . they are relatively prime

gcd = 1 = 1047*(-47) + 259* (190)

4)

a) for every prime number p in the domain we have

largest prime divisor of a prime is itself. so

f(p) = p

so the range contains all prime numbers .

b) No , f is not one to one because

f(6) = 3

f(3) = 3

c) No , f is not onto because the range contains only prime numbers but not composite numbers.

d) f(1) does not exist . because 1 is neither prime nor composite.

5)

6) 242 = 15 * 16 + 2

242 = 2 (mod 15)

7)

8) 503 is prime

a^(p-1) congruent to 1 ( modulo p)

3^502 = 1 ( mod 503)

multiply both sides by 3

  3^503 = 3 ( mod 503)

3^505 = 27 (mod 503)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.