BSSE 21043 Number Theory Quiz

Questions and Answers

What is the primary focus of number theory?

The study of integers and their properties (correct)

The study of prime numbers

The study of the set of positive rational numbers

The study of real numbers and their applications

What arithmetic method is introduced in number theory for divisibility?

Algebraic arithmetic

Vector arithmetic

Modulo arithmetic (correct)

Euclidean arithmetic

Which algorithm is used to compute the greatest common divisors?

Lattice algorithm

Euclidean algorithm (correct)

Sieve method

Newton's method

Which of the following is NOT a topic covered in BSSE 21043?

Linear differential equations Signup and view all the answers

In which applications does number theory play a critical role?

Graph theory in software engineering Signup and view all the answers

Which of the following best describes 'divisibility' in number theory?

The ability of an integer to be divided by another without leaving a remainder Signup and view all the answers

Which of these topics is part of the fundamentals covered in this course?

Algebraic structures such as Groups and Fields Signup and view all the answers

What is an example of a reference used in the course?

Discrete Mathematics and Its Applications Signup and view all the answers

What does the notation gcd(a, b) represent?

The greatest common divisor of a and b Signup and view all the answers

When a is divided by d, what indicates that a is divisible by d?

a mod d = 0 Signup and view all the answers

Which of the following integers are relatively prime?

17 and 22 Signup and view all the answers

If a = 12 and b = -18, what is gcd(a, b)?

6 Signup and view all the answers

Which statement about the operators for modular arithmetic is false?

All languages handle mod with the same rules. Signup and view all the answers

What is the greatest common divisor of 24 and 36?

12 Signup and view all the answers

Which of the following correctly describes gcd(12, -16)?

4 Signup and view all the answers

How can the greatest common divisor of two integers be found?

By identifying all positive common divisors and choosing the largest Signup and view all the answers

What is the relationship between the product of two positive integers and their gcd and lcm?

$ab = gcd(a,b) imes lcm(a,b)$ Signup and view all the answers

What method is described as more efficient for finding the greatest common divisor?

Applying the Euclidean algorithm Signup and view all the answers

In the first step of calculating gcd(91, 287), what is the remainder when 287 is divided by 91?

14 Signup and view all the answers

After dividing 91 by 14, what is the result of the division and the remainder?

$91 = 14 imes 6 + 7$ Signup and view all the answers

What is the final result for gcd(91, 287) after performing the Euclidean algorithm?

7 Signup and view all the answers

Which of the following statements about divisors and remainders from the Euclidean algorithm is true?

Any divisor of $a$ and $b$ must also divide $b - ka$ for any integer $k$. Signup and view all the answers

What final equation represents the gcd of the original numbers using the backward substitution method?

$gcd(287, 91) = -6 imes 287 + 19 imes 91$ Signup and view all the answers

Why is the Euclidean algorithm preferred over direct computation for gcd?

It needs fewer calculations than prime factorization. Signup and view all the answers

What does gcd(a, b) represent in the context of the equations provided?

The highest common factor of a and b Signup and view all the answers

In the linear combination gcd(a, b) = sa + tb, what do s and t represent?

Integer coefficients Signup and view all the answers

Which equation represents the first step in calculating gcd for the numbers 414 and 662?

662 = 414 * 1 + 248 Signup and view all the answers

What is the last non-zero remainder when calculating gcd(414, 662)?

2 Signup and view all the answers

From the equations derived, what is s when gcd(414, 662) is expressed as a linear combination?

8 Signup and view all the answers

Which of the following equations correctly follows the process of working backwards from the Euclidean algorithm?

2 = 166 - 82 * 2 Signup and view all the answers

What is the significance of the equation r_n = sa + tb in the Euclidean algorithm?

It finds the greatest common divisor of a and b Signup and view all the answers

What form does the linear combination take in order to express the gcd of two integers?

sa + tb Signup and view all the answers

Upon finishing the calculations, what will always be the value of gcd(a, b)?

The smallest integer that can divide both a and b Signup and view all the answers

Which sequence correctly summarizes the steps using the division algorithm to find the gcd of 414 and 662?

662, 414, 248, 166, 82, 2 Signup and view all the answers

What is Bézout's identity in the context of the greatest common divisor?

It states that the gcd of two integers can be expressed as a linear combination of the integers. Signup and view all the answers

If $gcd(a, b) = s imes a + t imes b$, what does it indicate about the integers 𝑎 and 𝑏?

They can be expressed in terms of their gcd. Signup and view all the answers

What are the integers 𝑠 and 𝑡 called when expressing the gcd as a linear combination?

Bézout coefficients. Signup and view all the answers

Under what condition are two integers considered relatively prime?

Their gcd can be expressed as 1. Signup and view all the answers

What does the equation $gcd(252, 198) = 4 imes 252 + (-5) imes 198$ represent?

The end result of expressing gcd as a linear combination. Signup and view all the answers

Which division from the Euclidean algorithm is critical for expressing $gcd(252,198)$ as a linear combination?

54 = 36 ∙ 1 + 18. Signup and view all the answers

What is the significance of the value 18 in the context of $gcd(252, 198)$?

It is the calculated gcd of the two integers. Signup and view all the answers

Which of the following statements is true regarding integers when using Bézout's theorem?

There exist integers s and t such that their linear combination equals their gcd. Signup and view all the answers

Study Notes

Course Overview

Course Code: BSSE 21043 - Mathematics for Software Engineering II
Instructor: Prof. N.G.J. Dias, Senior Professor, Department of Computer Systems Engineering, University of Kelaniya
Main Topics:
- Number Theory
- Graph Theory
- Algebraic Structures
- Combinatorics Applications

Evaluation Criteria

End of Semester Examination: 60%
Mid Semester Examination: 20%
Assignments (2): 20%

Number Theory

Definition: Study of integers and their properties.
Key Concepts:
- Divisibility and modular arithmetic.
- Greatest common divisor (gcd) and least common multiple (lcm).
Divisibility: Integer ( a ) is divisible by positive integer ( d ) if ( a \mod d = 0 ).

Modular Arithmetic

Operators: Different programming languages use various symbols for mod (e.g., mod, %, rem).
Operators may yield different results for negative integers, requiring careful usage.

Greatest Common Divisor (gcd)

Definition: gcd of integers ( a ) and ( b ) is the largest integer ( d ) such that ( d|a ) and ( d|b ).
Notation: ( \text{gcd}(a, b) ).
Existence: gcd exists because the set of common divisors is non-empty and finite.
Relatively Prime: Two integers ( a ) and ( b ) are relatively prime if ( \text{gcd}(a, b) = 1 ).

Finding gcd

Common Method: List and identify positive common divisors.
Example:
- ( \text{gcd}(24, 36) = 12 )
- ( \text{gcd}(17, 22) = 1 ) (relatively prime).

Euclidean Algorithm

Purpose: Efficient method for computing gcd without prime factorization.
Process: Repeatedly apply division. For integers ( a ) and ( b ):
1. Divide ( a ) by ( b ).
2. Replace ( a ) with ( b ) and ( b ) with the remainder.
3. Repeat until remainder is zero; last non-zero remainder is gcd.

Example using the Euclidean Algorithm

Find ( \text{gcd}(91, 287) ):
- Step 1: ( 287 = 91 \times 3 + 14 )
- Step 2: ( 91 = 14 \times 6 + 7 )
- Step 3: ( 14 = 7 \times 2 + 0 )
- Thus, ( \text{gcd}(91, 287) = 7 ).

Bézout's Theorem

States that gcd can be expressed as a linear combination of integers:
- ( \text{gcd}(a, b) = sa + tb ) for some integers ( s ) and ( t ).
Bézout Coefficients: Integers ( s ) and ( t ) satisfying Bézout's identity.

Corollary

Positive integers ( a ) and ( b ) are relatively prime if and only if there exist integers ( s ) and ( t ) such that ( sa + tb = 1 ).

Applications

Number theory and graph theory have critical applications in software engineering, particularly in algorithms and data structures.

Studying That Suits You

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

Description

Test your understanding of Number Theory as part of the BSSE 21043 course. This quiz covers key concepts such as divisibility, modular arithmetic, and the greatest common divisor. Challenge yourself and reinforce your knowledge in this essential topic for software engineering.