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 (B)

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. (B), 2 and 8, since 2 is a factor of 8. (C)</p> Signup and view all the answers

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

<p>False (B)</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 (B)</p> Signup and view all the answers

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

<p>True (A)</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 (A)</p> Signup and view all the answers

The base of the binary numeral system is 10.

<p>False (B)</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 (D)</p> Signup and view all the answers

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

<p>True (A)</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 (D)</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 (A)</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 (B)</p> Signup and view all the answers

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

<p>11110 (C)</p> Signup and view all the answers

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

<p>False (B)</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 (B)</p> Signup and view all the answers

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

<p>(001 101 000 000)2 (D)</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 (B)</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 (D)</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 (B)</p> Signup and view all the answers

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

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

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

<p>False (B)</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 (C)</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

Flashcards

Divides Operator (|)

The symbol '|' is used to indicate when one integer divides another integer evenly. This means there exists an integer 'c' such that 'a * c = b' where 'a' divides 'b'.

Not-Divides Operator (∤)

The symbol '∤' indicates that one integer does not divide another integer evenly. There is no integer 'c' such that 'a * c = b' where 'a' does not divide 'b'.

Factor

A factor of an integer 'b' is any integer 'a' that evenly divides 'b'.

Multiple

A multiple of an integer 'a' is any integer 'b' that is evenly divisible by 'a'.

Signup and view all the flashcards

a | b

The expression 'a | b' reads as 'a divides b', meaning there exists an integer 'c' where 'a * c = b'.

Signup and view all the flashcards

5 ∤ 12

The expression '5 ∤ 12' reads as '5 does not divide 12', meaning there is no integer 'c' where '5 * c = 12'.

Signup and view all the flashcards

3 | -12 is True

The statement 3 | -12 is true because there exists an integer 'c' (in this case, -4) where '3 * -4 = -12'.

Signup and view all the flashcards

3 | 7 is False

The statement 3 | 7 is false because there is no integer 'c' where '3 * c = 7'.

Signup and view all the flashcards

Divides Relation (a | b)

An integer a divides an integer b (written as a | b) if there exists an integer c such that b = ac. In other words, b is a multiple of a.

Signup and view all the flashcards

Divides Relation Properties

The divides relation has several important properties, including:

  1. a | 0
  2. (a | b and a | c) → a | (b + c)
  3. a | b → a | bc
  4. (a | b and b | c) → a | c
Signup and view all the flashcards

Quotient (q)

The quotient is the result of dividing one number (the dividend) by another (the divisor). It represents how many times the divisor goes into the dividend.

Signup and view all the flashcards

Remainder (r)

The remainder is the amount left over after dividing one number (the dividend) by another (the divisor).

Signup and view all the flashcards

Modulo Operator (mod)

The modulo operator (mod) gives the remainder when one number (the dividend) is divided by another (the divisor).

Signup and view all the flashcards

What is 101 mod 11?

101 divided by 11 has a quotient of 9 and a remainder of 2. Therefore, 101 mod 11 equals 2.

Signup and view all the flashcards

Finding the Remainder (Positive Dividend)

To find the remainder (r) when dividing a positive number (a) by a positive divisor (d), repeatedly subtract the divisor from the dividend until the remaining value (r) is less than the divisor.

Signup and view all the flashcards

Finding the Remainder (Negative Dividend)

To find the remainder (r) when dividing a negative number (a) by a positive divisor (d), repeatedly add the divisor to the dividend until the resulting value is positive (or zero) and less than the divisor.

Signup and view all the flashcards

Modular Arithmetic

A system of arithmetic where numbers 'wrap around' after reaching a specific modulus (m). This means that two numbers are considered equivalent if their difference is divisible by the modulus.

Signup and view all the flashcards

Congruence Modulo m

Two integers 'a' and 'b' are congruent modulo 'm' if their difference (a - b) is divisible by 'm'. We write this as a ≡ b (mod m).

Signup and view all the flashcards

Find 'a mod m'

To find 'a mod m', calculate the remainder when 'a' is divided by 'm'. The result is the remainder, which is always a non-negative value less than 'm'.

Signup and view all the flashcards

Base b Number System

A system of representing numbers using a base 'b' with 'b' unique digits. Each digit position represents a power of the base.

Signup and view all the flashcards

Converting to Base b

To convert an integer 'n' to base 'b', repeatedly find the remainder 'n mod b' and divide 'n' by 'b' (integer division), until 'n' becomes zero. The remainders, in reverse order, represent the digits in base 'b'.

Signup and view all the flashcards

Convert Decimal to Binary

Convert a decimal number to its equivalent binary representation using repeated division by 2 and recording the remainders.

Signup and view all the flashcards

Binary Expansion

A representation of an integer using only the digits 0 and 1, where each position represents a power of 2.

Signup and view all the flashcards

Decimal Expansion of Binary

Calculating the equivalent decimal value of a binary number by summing the products of each digit and its corresponding power of 2.

Signup and view all the flashcards

Convert Decimal to Octal

Change a decimal number to its octal equivalent using repeated division by 8, noting the remainders.

Signup and view all the flashcards

Octal Expansion

A number system using eight distinct digits (0-7) where each place value represents a power of 8.

Signup and view all the flashcards

Decimal Equivalent of Octal

Finding the decimal value of an octal number by multiplying each digit by its corresponding power of 8 and summing the results.

Signup and view all the flashcards

Hexadecimal Expansion

A system using 16 distinct digits (0-9, A-F) with each place value representing a power of 16.

Signup and view all the flashcards

Convert Decimal to Hexadecimal

Transforming a decimal number to a hexadecimal representation by repeated division by 16, recording the remainders (0-9, A-F).

Signup and view all the flashcards

Binary to Octal Conversion

Convert a binary number to its equivalent octal representation by grouping the binary digits into blocks of three, starting from the rightmost digit. Add leading zeros if needed. Each block represents an octal digit.

Signup and view all the flashcards

Binary to Hexadecimal Conversion

Convert a binary number to its equivalent hexadecimal representation by grouping the binary digits into blocks of four, starting from the rightmost digit. Add leading zeros if needed. Each block represents a hexadecimal digit.

Signup and view all the flashcards

Decimal to Binary Conversion

Convert a decimal number to its equivalent binary representation by repeatedly dividing the decimal number by 2. The remainders from each division, read from bottom to top, form the binary representation.

Signup and view all the flashcards

Binary to Decimal Conversion

Convert a binary number to its equivalent decimal representation by summing the values of each digit multiplied by its corresponding power of 2, starting from the rightmost digit.

Signup and view all the flashcards

Binary Addition

Add binary numbers digit by digit, starting from the rightmost digit. If the sum of two digits is 2, write 0 and carry-over 1 to the next digit.

Signup and view all the flashcards

Binary Multiplication

Multiply binary numbers similar to decimal multiplication. For each digit in the multiplier, multiply the multiplicand by that digit, shifting the result one position to the left for each subsequent digit. Finally, sum all the partial products.

Signup and view all the flashcards

Integer Division (div)

The integer division operation (a div d) gives the whole number quotient when an integer 'a' is divided by another integer 'd', where 'd' is greater than 0. It discards any fractional part of the result.

Signup and view all the flashcards

Modular Exponentiation

A mathematical operation that efficiently calculates the remainder of a large integer raised to a power, modulo another integer. It's used in cryptography and other areas.

Signup and view all the flashcards

Binary Representation

A way to represent any number using only 0s and 1s. Each digit's position represents a power of 2.

Signup and view all the flashcards

Finding 3644 (mod 645)

This problem involves calculating the remainder when 3644 is divided by 645. It can be solved efficiently using modular exponentiation.

Signup and view all the flashcards

Sum and Product in Binary

Adding or multiplying numbers expressed in binary format. You perform the operations digit by digit, carrying over values as needed.

Signup and view all the flashcards

7644 (mod 645)

Similar to finding 3644 mod 645, you need to compute the remainder when 7644 is divided by 645. Use modular exponentiation to solve it.

Signup and view all the flashcards

Binary Addition/Multiplication

The process of adding or multiplying binary numbers, taking into account the place values and carrying over as needed.

Signup and view all the flashcards

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

Use Quizgecko on...
Browser
Open
Browser
Browser