EMath 105 - Discrete Mathematics I: Number Theory
47 Questions
2 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

When we say that 3 divides 12, which of the following statements is true?

  • 3 is greater than 12.
  • There is an integer that multiplied by 3 equals 12. (correct)
  • 12 is a factor of 3.
  • 3 does not divide 12.

    • 5 divides 12 is true.

    False

    What is the notation for saying that 3 does not divide 12?

    5 ∤ 12

    If a does not divide b, we write it as a ______ b.

    <p>∤</p> Signup and view all the answers

    Match the following terms with their definitions:

    <p>Divides = There is an integer that multiplied by a equals b. Factor = An integer that can divide another integer evenly. Multiple = An integer that results from multiplying a factor by an integer.</p> Signup and view all the answers

    Which of the following pairs correctly demonstrates the relationship between factors and multiples?

    <p>7 and 14, since 14 is a multiple of 7.</p> Signup and view all the answers

    If a divides b, then a is a multiple of b.

    <p>False</p> Signup and view all the answers

    Give an example of two integers where the first is a factor of the second.

    <p>3 and 12</p> Signup and view all the answers

    What is the hexadecimal representation of the decimal number 23670?

    <p>5C76</p> Signup and view all the answers

    The binary expansion (11011)2 equals 27 in decimal.

    <p>True</p> Signup and view all the answers

    What is the decimal expansion of the octal number (111)8?

    <p>73</p> Signup and view all the answers

    (101011111)2 in decimal is equal to ______.

    <p>351</p> Signup and view all the answers

    Match the following numeral systems with their respective base:

    <p>Binary = Base 2 Octal = Base 8 Decimal = Base 10 Hexadecimal = Base 16</p> Signup and view all the answers

    Which of the following digits is NOT used in hexadecimal?

    <p>G</p> Signup and view all the answers

    The base of the binary numeral system is 10.

    <p>False</p> Signup and view all the answers

    How many digits are used in the octal numeral system?

    <p>8</p> Signup and view all the answers

    What is the result of 228 mod 119?

    <p>90</p> Signup and view all the answers

    The statement 21 ≡ −8 (mod 6) is true.

    <p>True</p> Signup and view all the answers

    What is the octal representation of the binary number (011 111 010 111 100)2?

    <p>(37274)8</p> Signup and view all the answers

    Calculate the value of -10101 mod 333.

    <p>231</p> Signup and view all the answers

    The hexadecimal representation of the binary number (0011 1110 1011 1100)2 is (3EBC)16.

    <p>True</p> Signup and view all the answers

    To convert the number 25 into binary, the last digit is obtained by computing 25 mod ______.

    <p>2</p> Signup and view all the answers

    Convert the decimal number 231 to its binary expansion.

    <p>11100111</p> Signup and view all the answers

    To convert to octal, group the binary digits into blocks of ____.

    <p>three</p> Signup and view all the answers

    Match the bases with their corresponding number of digits:

    <p>Decimal = 10 Binary = 2 Octal = 8 Hexadecimal = 16</p> Signup and view all the answers

    Match the numbers with their corresponding binary expansions:

    <p>(572)8 = (101 111 010)2 (1604)8 = (001 101 000 000)2 (423)8 = (100 001 011)2 (2417)8 = (101 001 001 111)2</p> Signup and view all the answers

    Which of the following is NOT a valid representation of base 16?

    <p>0, 1, 2, 3, G</p> Signup and view all the answers

    What is the result of $110 \times 101$ in binary?

    <p>11110</p> Signup and view all the answers

    The number 53 ≡ 108 (mod 7) is true.

    <p>False</p> Signup and view all the answers

    In modular arithmetic, the operation 'mod' can yield a result that is greater than the divisor.

    <p>False</p> Signup and view all the answers

    What is the binary expansion of the octal number (1604)8?

    <p>(001 101 000 000)2</p> Signup and view all the answers

    What are the digits used in base 8?

    <p>0, 1, 2, 3, 4, 5, 6, 7</p> Signup and view all the answers

    What is the purpose of modular exponentiation?

    <p>To efficiently compute large powers with respect to a modulus.</p> Signup and view all the answers

    The product of binary numbers (110)2 and (101)2 is (11110)2.

    <p>False</p> Signup and view all the answers

    What is the binary result of the addition of (1110)2 and (1011)2?

    <p>11001</p> Signup and view all the answers

    Given integers a and d, d > 0, the quotient is defined as a div d and the remainder is defined as a mod _____.

    <p>d</p> Signup and view all the answers

    Match the binary numbers with their decimal equivalents:

    <p>0100 0111 = 71 0111 0111 = 119 1110 1111 = 239 1011 1101 = 189</p> Signup and view all the answers

    When performing modular operations, what is a common technique for the exponent?

    <p>Convert to binary</p> Signup and view all the answers

    What is the initial value of x set to in the modular exponentiation algorithm?

    <p>1</p> Signup and view all the answers

    The algorithm for division and modulus requires that the divisor must be equal to or less than the dividend.

    <p>False</p> Signup and view all the answers

    If 5 | 25 and 5 | 30, what can be concluded?

    <p>5 | (25 + 30)</p> Signup and view all the answers

    If a | b and b | c, then it is false that a | c.

    <p>False</p> Signup and view all the answers

    What are the quotient and remainder when 101 is divided by 11?

    <p>Quotient is 9, Remainder is 2</p> Signup and view all the answers

    In the equation $101 = 11 \times 9 + 2$, the number 11 is called the ______.

    <p>divisor</p> Signup and view all the answers

    When 25 is divided by 5, what is the remainder?

    <p>0</p> Signup and view all the answers

    Given a = -7 and d = 3, what are the values of q and r?

    <p>q = -3, r = 2</p> Signup and view all the answers

    If a | b and a | c, then a | ______ + nc whenever n is any integer.

    <p>mb</p> Signup and view all the answers

    Study Notes

    EMath 105 - Discrete Mathematics I for SE

    • Course title: EMath 105 - Discrete Mathematics I for SE
    • Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department

    Number Theory

    • Number theory is the study of integers, their properties, and their relationship to algorithms.
    • Number theory is important in many modern algorithms. This includes hash functions, cryptography, digital signatures, and online security.

    The Integers and Division

    • Students are already familiar with integers and division.
    • Specific notations, terminology, and theorems, not previously known to the students, form the basics of number theory.

    The Divides Operator

    • Notation: 3 | 12 means 3 evenly divides 12
    • Notation: 5 \ 12 means 5 does not evenly divide 12
    • Read '3 | 12' as '3 divides 12'
    • Read '5 \ 12' as '5 does not divide 12'

    Divides, Factor, Multiple Relationship

    • Definition: a | b (a divides b) means there is an integer c such that b = a * c.
    • If a | b, then a is a factor or divisor of b and b is a multiple of a.
    • Example: 3 | -12 is True, but 3 | 7 is False.

    Results on the Divides Operator

    • If a | b and a | c, then a | (b + c).
    • If a | b, then a | bc for all integers c.
    • If a | b and b | c, then a | c.
    • Example: If 5 | 25 and 5 | 30, then 5 | (25 + 30).

    Divides Relation

    • Theorem: For any integers a, b, and c:
      • a | 0
      • If a | b and a | c, then a | (b + c)
      • a | b implies a | bc for any integer c
      • If a | b and b | c, then a | c
    • Corollary: If a | b and a | c, then a | (mb + nc) for any integers m and n.

    Quotient and Remainder

    • When dividing a by d, q is the quotient, and r is the remainder.
    • a = d * q + r, where 0 ≤ r < d.
    • q = quotient r = remainder d = divisor a = dividend
    • Examples provided: Calculations of 101 / 11 and more examples with different values.

    Modular Arithmetic

    • "a is congruent to b modulo m" if m | (a - b).
    • Notation: a ≡ b (mod m).
    • Example: 17 ≡ 5 (mod 6) because 6 | (17 - 5).

    Exercises (True/False)

    • Identify whether statements like 7 ≡ 19 (mod 3) are True or False.

    Number Systems

    • Discusses the decimal, binary, octal, and hexadecimal number systems.
    • Decimal uses digits 0-9.
    • Binary uses digits 0 and 1.
    • Octal uses digits 0-7.
    • Hexadecimal uses digits 0-9 and letters A-F (representing 10-15).

    Bases of Particular Interest

    • Decimal (base 10): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 as digits.
    • Binary (base 2): 0, 1 as digits.
    • Octal (base 8): 0, 1, 2, 3, 4, 5, 6, 7 as digits.
    • Hexadecimal (base 16): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F as digits.

    Table: Representation of Integers 0-15

    • Table showing the hexadecimal, octal, and binary representations of integers 0 through 15.

    Converting to Base b

    • Algorithm to convert an integer to a different base b.
    • Find the rightmost digit by calculating the remainder when dividing by b.
    • Recursively apply the process to the quotient, until the quotient becomes 0.

    Converting 25 to Binary

    • Detailed example of converting 25 to binary representation using the successive division method.

    Converting 23670 to Hexadecimal

    • Illustrated example of converting 23,670 to hexadecimal.

    Binary Expansions

    • Most computers use binary expansions.
    • Examples of converting binary to decimal and vice versa.

    Octal Expansions

    • Conversion examples and an example problem.

    Hexadecimal Expansions

    • Conversion examples.

    Base Conversion

    • Algorithm to convert an integer to any other base b.

    Conversion from/to Binary, Octal and Hexadecimal

    • Example problem converting one base to another.

    Algorithm for Integer Operations

    • Binary addition algorithm.
    • Binary multiplication algorithm.
    • Algorithm for finding the quotient and the remainder of a division.
    • Algorithm for modular exponentiation.

    Exercises

    • Problems to practice conversion between different bases.
    • Problems involving binary addition, multiplication, and modular exponentiation.

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Discrete Mathematics Chapter 3 Number Theory PDF

    Description

    This quiz covers key concepts in number theory from EMath 105 - Discrete Mathematics I for SE. Students will learn about integers, division, and the divides operator, along with their relationships in algorithms. Prepare to explore the foundational theorems and notations essential for understanding modern cryptography and security algorithms.

    More Like This

    Number Theory Basics
    9 questions

    Number Theory Basics

    LawAbidingPalmTree avatar
    LawAbidingPalmTree
    Exploring Number Theory: Secrets of Integers and Primes
    12 questions

    Quiz on Integers: Most Divisors in Number Theory

    HealthfulFermium avatar
    HealthfulFermium
    Exploring Number Theory Concepts
    12 questions

    Exploring Number Theory Concepts

    CleanlyKoto avatar
    CleanlyKoto
    Number Theory Quiz
    8 questions

    Number Theory Quiz

    DazzledBarium avatar
    DazzledBarium
    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser