# Introduction to Number Theory

Section 5.1 Introduction to Number Theory

2. When n = 47, the algorithm would check if the numbers 2, 3, 4, 5, and 6 (round
down √47 to the nearest integer) are divisors of 47.
N one of these integers divide 47, and the algorithm would de termine that 47 is
prime
and return 0.

3. When n = 209 a quick computation shows that the algorithm would check the
integers 2, 3, 4, …, 14 in order to find any possible divisors. When it checks 11,
the algorithm will find that 11 does divide 209 and return the number 11.

12. gcd(0,17) = 17 According to the definition in the book any non- zero number is
a divisor of 0, so the greatest divisor common to both is 17.

14. gcd(60,90) = 30

15. 110 = 2 • 5 •11 and 273 = 3• 7 •13 so gcd(110,273) = 1

17. 315 = 32 • 5 • 7 and 825 = 3• 52 •11 so gcd(315,825)= (3)(5)=15

22. gcd(15,159 ) =15 (This fol lows from theorem 5.1.25 for instance.

25.
lcm (0,17) = 0
lcm(60,90) =180
lcm(110,273) = 2• 3• 5• 7•11•13 = 30030
lcm(315,825) = 32 • 52 • 7•11=17,325   lcm(15,159) =159

29. If d1 |m and d2 | n then m = p ۰ d1 and n = q ۰  d2 for some integers p and q
but then mn = pq• d1d2 and hence d1d2 | mn.

30. If dc | nc, then nc = q ۰ dc.
This implies that n = qd, hence d | n

Section 5.2 Re presentation of Integers and Integer Algorithms.

1. 60 (decimal) = 111100 (base 2), so it takes 6 bits to represent this number.

2. 63 (decimal) = 111111 (base 2), so it takes 6 bits.

5. 128 (decimal) = 10000000 (base 2). So it takes 8 bits.

8. 1001 -> 9

9. 11011 -> 27

10. 11011011 -> 219

14. 34 -> 100010

16. 223 -> 11011111

17. 400 -> 110010000

20. 1001 + 1111 = 11000

22. 110110 + 101101 = 1100011

23. 101101 + 11011 = 1001000

26. 3A -> 58

27. 1E9 -> 489

28. 3E7C -> 15,996

35. 4A + B4 = FE ( hex addition )

36. 195 + 76E = 903 (hex addition)

40. 2010 can represent a number in decimal (the regular number 2,010) or
hexadecimal (this would represent the decimal number 8,208), but not in binary
(the latter does not allow for a 2)

41. 1101010 can represent a number in binary, decimal and hexadecimal.

56. See the back of the book.

57. Use the explanation in example 5.2.15 as an example.
If n = 15 we trace through the algorithm updating result = result*x every time n is
odd. We update x to be x*x every time we execute a loop.
x Current value of n N mod 2 Result = result*x New n

 x Current value of n N mod 2 N mod 2 New n a 15 1 a 7 a2 7 1 a3 3 a4 3 1 a7 1 a8 1 1 a15 0
 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of February 18th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!