Find study content
Learning Materials

Discover learning materials by subject, university or textbook.

Explanations

Textbooks

Exams
All Subjects

Anthropology

Archaeology

Architecture

Art and Design

Bengali

Biology

Business Studies

Greek

Chemistry

Chinese

Combined Science

Computer Science

Economics

Engineering

English

English Literature

Environmental Science

French

Geography

German

History

Hospitality and Tourism

Human Geography

Italian

Japanese

Law

Macroeconomics

Marketing

Math

Media Studies

Medicine

Microeconomics

Music

Nursing

Nutrition and Food Science

Physics

Polish

Politics

Psychology

Religious Studies

Sociology

Spanish

Sports Sciences

Translation

All Subjects

Biology

Business Studies

Chemistry

Combined Science

Computer Science

Economics

English

Environmental Science

Geography

History

Math

Physics

Psychology

Sociology

EXAM TYPES

GCSE

IGCSE

AS

A Level

International A Level

University Admissions Tests

GCSE SUBJECTS

GCSE 1

GCSE 2

GCSE 3

GCSE 4

GCSE 5

SOME-TEXT

IGCSE SUBJECTS

IGCSE 1

AS SUBJECTS

AS 1

A Level SUBJECTS

A Level 1

International A Level SUBJECTS

International A Level 1

University Admissions Tests SUBJECTS

University Admissions Tests 1
Features
Features

Discover all of these amazing features with a free account.

Flashcards

Vaia AI

Notes

Study Plans

Study Sets
What’s new?

Flashcards
Study your flashcards with three learning modes.

Study Sets
All of your learning materials stored in one place.

Notes
Create and edit notes or documents.

Study Plans
Organise your studies and prepare for exams.
Resources
Discover

All the hacks around your studies and career - in one place.

Find a job

Find a degree

Student Deals

Magazine

Mobile App
Featured

Magazine
Trusted advice for anyone who wants to ace their studies & career.

Job Board
The largest student job board with the most exciting opportunities.

Vaia Deals
Verified student deals from top brands.

Our App
Discover our mobile app to take your studies anywhere.

Go to App

Learning Materials

Features

Discover

Algorithms

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani

Computer Science

1st Edition · 333 pages

ISBN: 9780073523408

Chapter 1: Q25E (page 49)

Calculate $2^{125} \mod 127$ using any method you choose. (Hint: 127 is prime.)

Short Answer

Expert verified

$2^{125} \mod 127$ is equal to

Step by step solution

01

Given condition

To find the modulo of any large number we can divide that number into small parts and find the modulo of the smaller part and recognized the pattern to get the answer of the large integer.

02

Calculate 2125mod127

For, $2^{125} \mod 127$ , we can write $2^{125}$ as

$2^{125} = 2^{7 (17) + 6}$

Where $2^{7} \mod 127$ can be written as,

$2^{7} \mod 127 = 128 \mod 127 = 1$

Then, for $2^{125} \mod 127$ , we have,

$2^{125} \mod 127 = 2^{7 (17) + 6} \mod 127 = 2^{7 (17)} . 2^{6} \mod 127 = 1^{17} . 2^{6} \mod 127 = 64 \mod 127 = 64$

So, $2^{125} \mod 127$ is equal to 64.

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

1.37. The Chinese remainder theorem.
(a) Make a table with three columns. The first column is all numbers from 0 to 14. The second is the residues of these numbers modulo 3; the third column is the residues modulo 5. What do we observe?
(b) Prove that if p and q are distinct primes, then for every pair (j, k) with $0 \leq j < q$ and $0 \leq k < q$ , there is a unique integer $0 \leq i < pq$ such that $i \equiv j \mod p$ and $i \equiv k \mod q$ . (Hint:
Prove that no two different i's in this range can have the same (j, k), and then count.)
(c) In this one-to-one correspondence between integers and pairs, it is easy to go from i to (j, k). Prove that the following formula takes we the other way:
$i = {j . q (q^{- 1} \mod p) + kp (p^{- 1} \mod q)} modpq$
(d) Can we generalize parts (b) and (c) to more than two primes?

How many integers modulo $11^{3}$ have inverses? $(Note : 11^{3} = 1331)$

Let $[m]$ denote the set ${0, 1, \dots, m - 1}$ . For each of the following families of hash functions, say whether or not it is universal, and determine how many random bits are needed to choose a function from the family.

(a) $H = {h_{a_{1}, a_{2}} : a_{1}, a_{2} \in [m]}$ , where $m$ is a fixed prime and

$h_{a_{1}} \cdot h_{a_{1}, a_{2}} (x_{1}, x_{2}) = a_{1} x_{1} + a_{2} x_{2} m o d m$

Notice that each of these functions has signature $h_{a_{1}, a_{2}} : {[m]}^{2} \to [m]$ that is, it maps a pair of integers in $[m]$ to a single integer in $[m]$ .

(b) $H$ is as before, except that now $m = 2^{k}$ is some fixed power of. $2$

(c) $H$ is the set of all functions $f : [m] \to [m - 1]$ .

1.38. To see if a number, say $562437487$ , is divisible by $3$ , you just add up the digits of its decimalrepresentation, and see if the result is divisible by role="math" localid="1658402816137" $3$ .

( $5 + 6 + 2 + 4 + 3 + 7 + 4 + 8 + 7 = 46$ , so it is not divisible by $3$ ).

To see if the same number is divisible by $11$ , you can do this: subdivide the number into pairs ofdigits, from the right-hand end $(87, 74, 43, 62, 5)$ , add these numbers and see if the sum is divisible by $11$ (if it's too big, repeat).

How about $37$ ? To see if the number is divisible by $37$ , subdivide it into triples from the end $(487, 437, 562)$ add these up, and see if the sum is divisible by $37$ .

This is true for any prime $p$ other than $2$ and $5$ . That is, for any prime $p≠2,5$ , there is an integer $r$ such that in order to see if $p$ divides a decimal number $n$ , we break $n$ into $r$ -tuples of decimal digits (starting from the right-hand end), add up these $r$ -tuples, and check if the sum is divisible by $p$ .

(a) What is the smallest $r$ such for $p=13$ ? For $p=13$ ?

(b) Show that $r$ is a divisor of $p-1$ .

Show that if a has a multiplicative inverse modulo N, then this inverse is unique (modulo N).

See all solutions

Recommended explanations on Computer Science Textbooks

Databases

Read Explanation

Data Representation in Computer Science

Read Explanation

Game Design in Computer Science

Read Explanation

Computer Network

Read Explanation

Computer Organisation and Architecture

Read Explanation

Functional Programming

Read Explanation

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free