1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Ilya [14]
3 years ago
9

Solve the following equations: (a) x^11=13 mod 35 (b) x^5=3 mod 64

Mathematics
1 answer:
tino4ka555 [31]3 years ago
5 0

a.

x^{11}=13\pmod{35}\implies\begin{cases}x^{11}\equiv13\equiv3\pmod5\\x^{11}\equiv13\equiv6\pmod7\end{cases}

By Fermat's little theorem, we have

x^{11}\equiv (x^5)^2x\equiv x^3\equiv3\pmod5

x^{11}\equiv x^7x^4\equiv x^5\equiv6\pmod 7

5 and 7 are both prime, so \varphi(5)=4 and \varphi(7)=6. By Euler's theorem, we get

x^4\equiv1\pmod5\implies x\equiv3^{-1}\equiv2\pmod5

x^6\equiv1\pmod7\impleis x\equiv6^{-1}\equiv6\pmod7

Now we can use the Chinese remainder theorem to solve for x. Start with

x=2\cdot7+5\cdot6

  • Taken mod 5, the second term vanishes and 14\equiv4\pmod5. Multiply by the inverse of 4 mod 5 (4), then by 2.

x=2\cdot7\cdot4\cdot2+5\cdot6

  • Taken mod 7, the first term vanishes and 30\equiv2\pmod7. Multiply by the inverse of 2 mod 7 (4), then by 6.

x=2\cdot7\cdot4\cdot2+5\cdot6\cdot4\cdot6

\implies x\equiv832\pmod{5\cdot7}\implies\boxed{x\equiv27\pmod{35}}

b.

x^5\equiv3\pmod{64}

We have \varphi(64)=32, so by Euler's theorem,

x^{32}\equiv1\pmod{64}

Now, raising both sides of the original congruence to the power of 6 gives

x^{30}\equiv3^6\equiv729\equiv25\pmod{64}

Then multiplying both sides by x^2 gives

x^{32}\equiv25x^2\equiv1\pmod{64}

so that x^2 is the inverse of 25 mod 64. To find this inverse, solve for y in 25y\equiv1\pmod{64}. Using the Euclidean algorithm, we have

64 = 2*25 + 14

25 = 1*14 + 11

14 = 1*11 + 3

11 = 3*3 + 2

3 = 1*2 + 1

=> 1 = 9*64 - 23*25

so that (-23)\cdot25\equiv1\pmod{64}\implies y=25^{-1}\equiv-23\equiv41\pmod{64}.

So we know

25x^2\equiv1\pmod{64}\implies x^2\equiv41\pmod{64}

Squaring both sides of this gives

x^4\equiv1681\equiv17\pmod{64}

and multiplying both sides by x tells us

x^5\equiv17x\equiv3\pmod{64}

Use the Euclidean algorithm to solve for x.

64 = 3*17 + 13

17 = 1*13 + 4

13 = 3*4 + 1

=> 1 = 4*64 - 15*17

so that (-15)\cdot17\equiv1\pmod{64}\implies17^{-1}\equiv-15\equiv49\pmod{64}, and so x\equiv147\pmod{64}\implies\boxed{x\equiv19\pmod{64}}

You might be interested in
PLZ HELP!!!! WILL GIVE BRAINLIEST + WORTH 10 POINTS!!! THX!!!!
mafiozo [28]

Answer:

I got this answer hope works...

5 0
3 years ago
Read 2 more answers
Choose the Athat seems to be congruent to the given one.
julia-pushkina [17]

Answer:

a. ∆EGF ≅ ∆EGD

Step-by-step explanation:

Congruent triangles would have the same side lengths and the same measure of angles.

From the figure given:

EG in ∆EGF ≅ EG in ∆EGD

GF in ∆EGF ≅ GD in ∆EGD, also

EF ≅ ED.

The three angles in ∆EFG are also congruent to the three angles in ∆EGD.

Therefore, ∆EGD is congruent to ∆EGF.

∆EGF ≅ ∆EGD

7 0
2 years ago
Jane is helping the librarian stack books on some new shelves. She is to stack 116 books on 16 shelves. The librarian told her t
goblinko [34]

Answer:

No

Step-by-step explanation:

This is not possible for Jane to put the same amount it all depends on how the book fits, how thick it is, how skinny it is and what else is on the shelf.

4 0
3 years ago
Read 2 more answers
Solve using substitution y=x-3 4x+y=32
hichkok12 [17]
Hey there !

Check the attachment.
Hope it helps you :)

7 0
2 years ago
Which statement is true?
Lera25 [3.4K]

Answer:

C is true as 2 pionts = a line

Step-by-step explanation:

I'm smartest in my class

6 0
2 years ago
Other questions:
  • I need help with this quick
    9·1 answer
  • The equation of a circle is ​ (x−10)² + (y−8)² = 256 ​
    11·1 answer
  • 60,000 ones equals how many thousands
    15·1 answer
  • Is this set of ordered pairs<br> a function?<br> (2,6), (4,9) (-2,6), (14, 11)
    9·1 answer
  • The following chart shows the times of runners in the 100 meter sprint.
    11·1 answer
  • PLEASE HELP QUICK!!<br><br> Factor!<br><br> b6–(x–4b3)2
    13·2 answers
  • Bob drove 65 miles per hour for 3 hours, how far did he drive​
    9·2 answers
  • I'm confused on the error and how to do the correct work.​
    9·1 answer
  • Factor<br> 10x + 100x + 250
    9·2 answers
  • -3x-8&gt;19?I have to solve for x
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!