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
Helpppp plz??????????????
professor190 [17]

Answer:

6/54 or 1/9

Step-by-step explanation:

6/54 reduces to 1/9

hope this helps

8 0
3 years ago
Find the number n that fits all of the conditions
finlep [7]
Your answer would be 12
7 0
3 years ago
Kylee frove 131.5 miles on Monday. On Tuesday she had to drive 213.27 miles. How much farther did she drive on Tuesday than on M
salantis [7]
Kylee drove 81.77 more miles on Tuesday.
8 0
3 years ago
54 is 75% of
VLD [36.1K]
54 is 75% of x.

75% of x:
75 \% \ of \ x=75\% \times x= \frac{75}{100}x=\frac{3}{4}x

75% of x is (3/4)x and 75% of x is 54. Set (3/4)x equal to 54:
\frac{3}{4}x=54 \\
x=54 \times \frac{4}{3} \\
x=\frac{54}{3} \times 4 \\
x=18 \times 4 \\
x=72

54 is 75% of 72.
3 0
3 years ago
Read 2 more answers
Can someone please help me with a math problem???? Thankyou in advance
almond37 [142]
What is the math problem??
8 0
3 years ago
Other questions:
  • Can 7 go into 42 and 91
    10·2 answers
  • Solve for x. |2x - 8| > 6
    10·2 answers
  • What is the simplest form for 9/3?
    13·2 answers
  • A phone company charges a flat rate of $15 to make phone calls for a month.they charge $0.10 per minute for each call made.if th
    10·2 answers
  • In your own words, describe to someone who knows only a little statistics how to recognize when an observation is an outlier. Wh
    13·1 answer
  • 5 * 3/5 i need help please
    9·1 answer
  • HELP ME, PLZ. 100 POINTS !!!
    6·1 answer
  • Emily earns extra spending money by babysitting children in her neighborhood. On Tuesday, she earned $16 for baby
    15·1 answer
  • Find slope and y-intercept
    14·1 answer
  • Graph: g(x)=5cos((\pi )/(2)x-(3\pi )/(2))-2
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!