Chapter 1: Q40E (page 52)

Show that if $x$ is a nontrivial square root of 1 modulo N , that is if $x^{2} \equiv 1 \mod N$ but $x \neq \pm 1 \mod N$ , then $N$ must be composite. (For instance, $4^{2} \equiv 1 \mod 15 but 4 ≢ \pm 1 \mod 15$ ; thus 4 is a nontrivial square root of 1 modulo 15.)

Short Answer

Expert verified

It can be proved by the proof by contradiction method.

Step by step solution

Explain composite numbers

The multiple of two small positive integers that has atleast one divisor other than one.

Prove the given problem

By proof by contradiction method, Consider If $x^{2} \equiv 1 \mod p, x \neq \pm 1 \mod p$ and is a prime number. Then,

$(x \mod p)^{2} - 1 \equiv 0 \mod p (x \mod p + 1) (x \mod p - 1) \equiv 0 \mod p$

Since, $x \neq \pm 1 m o d p$ , it is known that $1 \leq x m o d p - 1 < x m o d p + 1 < p,$ ,and P is a prime number. Knowing that $x m o d p \pm 1$ is relatively prime to p . Then by $(x \mod p + 1) (x \mod p - 1) \equiv 0 \mod p$ , according to the division theorems,

$x \mod p \pm 1 \equiv 0 \mod p$ , This is a contradiction.

So, p is a composite.

Therefore, it has been proved.

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!

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Show that if $x$ is a nontrivial square root of 1 modulo N , that is if $x^{2} \equiv 1 \mod N$ but $x \neq \pm 1 \mod N$ , then $N$ must be composite. (For instance, $4^{2} \equiv 1 \mod 15 but 4 ≢ \pm 1 \mod 15$ ; thus 4 is a nontrivial square root of 1 modulo 15.)

Short Answer

Step by step solution

Explain composite numbers

Prove the given problem

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Algorithms in Computer Science

Game Design in Computer Science

Theory of Computation

Computer Systems

Computer Programming

Data Structures

Study anywhere. Anytime. Across all devices.

Show that if xis a nontrivial square root of 1 modulo N , that is if x2≡1modNbut x≠±1modN, thenN must be composite. (For instance,42≡1mod15but4≢±1mod15; thus 4 is a nontrivial square root of 1 modulo 15.)

Short Answer

Step by step solution

Explain composite numbers

Prove the given problem

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Algorithms in Computer Science

Game Design in Computer Science

Theory of Computation

Computer Systems

Computer Programming

Data Structures

Study anywhere. Anytime. Across all devices.

Show that if $x$ is a nontrivial square root of 1 modulo N , that is if $x^{2} \equiv 1 \mod N$ but $x \neq \pm 1 \mod N$ , then $N$ must be composite. (For instance, $4^{2} \equiv 1 \mod 15 but 4 ≢ \pm 1 \mod 15$ ; thus 4 is a nontrivial square root of 1 modulo 15.)