Discrete Mathematics: Elementary and Beyond

6.10 How to Test Whether a Number is a Prime? 123

6.10.10 Show that a number with 30 digits cannot have more than 100 prime
factors.

6.10.11 Show that a number with 160 digits has a prime power divisor that is
at least 100. This is not true if we want a prime divisor that is at least 100.

6.10.12 Find the number of (positive) divisors ofn, for 1≤n≤20 (example:
6 has 4 divisors: 1, 2, 3, 6). Which of these numbers have an odd number of
divisors? Formulate a conjecture and prove it.

6.10.13 Find the g.c.d. of 100 and 254, using the Euclidean Algorithm.

6.10.14 Find pairs of integers for which the Euclidean Algorithm lasts (a) 2
steps; (b) 6 steps.

6.10.15 Recalling the Lucas numbersLnintroduced in Exercise 4.3.2, prove
the following:

(a) gcd(F 3 k,L 3 k)=2;

(b) ifnis not a multiple of 3, then gcd(Fn,Ln)=1;

(c) L 6 k≡2 (mod 4).

6.10.16 Prove that for every positive integermthere is a Fibonacci number
divisible bym(well, of course,F 0 = 0 is divisible by anym; we mean a larger
one).

6.10.17 Find integersxandysuch that 25x+41y=1.

6.10.18 Find integersxandysuch that

2 x+y≡4 (mod 17),

5 x− 5 y≡9 (mod 17).

6.10.19 Prove that^3

√

5 is irrational.

6.10.20 Prove that the two forms of Fermat’s Theorem, Theorem 6.5.1 and
(6.1), are equivalent.

6.10.21 Show that ifp>2 is a prime modulus, then

1

2

=

p+1

2

.

6.10.22 We are givenn+ 1 numbers from the set{ 1 , 2 ,..., 2 n}. Prove that
there are two numbers among them such that one divides the other.

6.10.23 What is the number of positive integers not larger than 210 and not
divisible by 2, 3 or 7?