By Practice 16, if p is prime then (p) = p 1. Prove that

Write gcd(308, 165) as a linear combination of 308 and 165

Write gcd(2420, 70) as a linear combination of 2420 and 70

Write gcd(735, 90) as a linear combination of 735 and 90

Write gcd(8370, 465) as a linear combination of 8370 and 465.

Write gcd(1326, 252) as a linear combination of 1326 and 252.

Write gcd(1018215, 2695) as a linear combination of 1018215 and 2695.

For Exercises 7–12, test whether n is prime and, if not, find its decomposition as a product of primes. n = 1729

For Exercises 712, test whether n is prime and, if not, find its decomposition as a product of primes n = 1789

For Exercises 712, test whether n is prime and, if not, find its decomposition as a product of primesn = 1171

For Exercises 712, test whether n is prime and, if not, find its decomposition as a product of primes. n = 1177

For Exercises 712, test whether n is prime and, if not, find its decomposition as a product of primes n = 8712

For Exercises 7–12, test whether n is prime and, if not, find its decomposition as a product of primes. n = 29575

Prove that for any positive integers a and b, a # b = gcd(a, b) # lcm(a, b). (Hint: consider both a and b in their factored form as a product of primes.)

Find gcd(2420, 70) by unique factorization into products of primes.

Find gcd(735, 90) by unique factorization into products of primes.

. The least common multiple of two positive integers a and b, lcm(a, b) is the smallest integer n such that a 0 n and b 0 n. Like the gcd(a, b), the lcm(a, b) can be found from the prime factorizations of a and b. Describe (in words) the gcd and the lcm in terms of the prime factors of a and b

Find gcd(1326, 252) by unique factorization into products of primes.

Find gcd(1018215, 2695) by unique factorization into products of primes

The least common multiple of two positive integers a and b, lcm(a, b) is the smallest integer n such that a 0 n and b 0 n. Like the gcd(a, b), the lcm(a, b) can be found from the prime factorizations of a and b. Describe (in words) the gcd and the lcm in terms of the prime factors of a and b.

Prove that for any positive integers a and b, a # b = gcd(a, b) # lcm(a, b). (Hint: consider both a and b in their factored form as a product of primes.)

For Exercises 2124, find the gcd and lcm of the two numbers given.a = 22 # 3 # 11, b = 2 # 3 # 112 # 13

For Exercises 2124, find the gcd and lcm of the two numbers given.

Find the gcd and lcm of the two numbers given. \(a=3 \cdot 5^{3} \cdot 11^{2}, b=3^{2} \cdot 5 \cdot 11 \cdot 17\)

For Exercises 2124, find the gcd and lcm of the two numbers given.

Prove that for any positive integers a and b, gcd(a, b) = gcd(a, a + b)

Prove that gcd(n, n + 1) = 1 for all positive integers n.

Find an example where n 0 ab but n | a and n | b. Does this violate the theorem of division by prime numbers?

The division of a full circle into 360 probably dates back to the early Persian calendar from around 700 b.c. that used 360 days in a year, so one day represented a rotation of 1/360 of other stars around the North Star. But it was also chosen because it is divisible by so many factors, avoiding the need to deal with fractions. Find the distinct nontrivial (but not necessarily prime) factors of 360.

Prove that there exist three consecutive odd positive integers that are prime numbers

Prove that for any positive integer n, there exist n consecutive composite numbers. [Hint: Start with (n + 1)! + 2]

Find \(\varphi(n)\) together with the numbers that give those values. n = 8

For Exercises 3134, find (n) together with the numbers that give those values.. n = 9

For Exercises 3134, find (n) together with the numbers that give those values.n = 10

For Exercises 3134, find (n) together with the numbers that give those values.n = 11

By Practice 16, if p is prime then (p) = p 1. Prove that this is an if and only if condition by proving that if (n) = n 1 for a positive integer n > 1, then n is prime

For any prime number p and any positive integer k, (pk ) = pk1 (p). Although this result follows directly from Equation (2) in this section, give a direct proof using the definition of the Euler phi function.

Compute \(\varphi\left(2^{4}\right)\) and state the numbers being counted. (Hint: See Exercise 36.)

Compute (33 ) and state the numbers being counted. (Hint: See Exercise 36.)

n = 117612 = 22 # 35 # 112

n = 233206 = 2 # 17 # 193

n = 1795625 = 54 # 132 # 17

n = 1,690,541,699 = 74 # 113 # 232

If p and q are prime numbers with p q, then (pq) = (p)(q). Although this result follows directly from Equation (2) in this section, give a direct proof using the definition of the Euler phi function.

Prove that if r and s are relatively prime, then (rs) = (r) (s).

Prove that for n and m positive integers, (nm) = nm1 (n)

Except for n = 2, all the values of (n) in Example 34 are even numbers. Prove that (n) is even for all n > 2.

A particular class of prime numbers is known as Mersenne primes, named for a French monk and mathematician of the seventeenth century who studied them. Mersenne primes are numbers of the form \(2^p ? 1\) where p is a prime, but not all numbers of this form are primes. For example, \(2^{11} ? 1 = 23 \cdot 89\) is not prime. The largest known prime number as of June 2013 is \(2^{57,885,161} ? 1\), a Mersenne prime. There happens to be a particularly efficient algorithm for testing numbers of the form \(2^p ? 1\) for primality, which is why almost all of the largest known primes are Mersenne primes. In recent years, most of these Marsenne primes have been discovered (and verified) by the GIMPS (Great Internet Mersenne Prime Search) distributed computing project, a worldwide group of volunteers who collaborate over the Internet to test for Mersenne primes. Find the first 4—the 4 smallest—Mersenne primes.

Goldbachs conjecture states that every even integer greater than 2 is the sum of two prime numbers. Verify Goldbachs conjecture for a. n = 8 b. n = 14 c. n = 28

A perfect number is a positive integer n that equals the sum of all divisors less than n. For example, 6 is a perfect number because 6 = 1 + 2 + 3. Perfect numbers are related to Mersenne primes (see Exercise 47) in that if p is a prime and 2p 1 is a prime, then 2p1 (2p 1) is a perfect number. (This result was proved by Euclid around 300 b.c.). For example, 6 = 21 (22 1). a. Prove that 28 is a perfect number by writing it as the sum of its divisors. b. Write 28 in the form 2p1 (2p 1).

a. Prove that 496 is a perfect number (see Exercise 49) by writing it as the sum of its divisors. b. Write 496 in the form 2p1 (2p 1).

An algorithm exists to find all prime numbers less than some given positive integer n. This method, called the Sieve of Eratosthenes, was discovered by Eratosthenes, a student of Plato. To carry out this algorithm, list all integers from 1 through n 1. Then make repeated passes through the list, on the first pass crossing out all multiples of 2 that are greater than 2. On the second pass cross out all multiples of 3 that are greater than 3. On the next pass, cross out all multiples of 5 that are greater than 5, and so forth for all primes less than !n. The numbers remaining when this process terminates are the primes less than n. Use the Sieve of Eratosthenes to find all prime numbers less than 100

a. Compute the square of 11. b. Compute the square of 111. c. Prove that any n-digit number consisting of all 1s, when squared, produces the number 123 (n 1)n(n 1) 321. A number that reads the same forward and backward is called a palindrome.

Sudoku puzzles are popular number-based puzzles. A game consists of a 9 9 grid made up of nine 3 3 blocks. Each row and each column of the game must contain exactly one of the 9 digits 1 9; furthermore, each 3 3 block must contain exactly one of the digits 1 through 9. Following is a sample puzzle, used by permission from Web Sudoku at http://www.websudoku.com, where you can generate puzzles at any of four levels of difficulty. Try completing this puzzle.