Mathematics, 23.11.2019 07:31 withrowrj

Find an integer x such that 0< =x< 527 and x^37===3 mod 527

Answers: 2

Show answers

Answers

Since $527=17\times31$ , we have that

$x^{37}\equiv3\mod{527}\implies\begin{cases}x^{37}\equiv3\mod{17}\\x^{37}\equiv3\mod{31}\end{cases}$

By Fermat's little theorem, and the fact that 37=2(17)+3=1(31)+6

, we know that

$x^{37}\equiv(x^2)^{17}x^3\equiv x^5\mod{17}$
$x^{37}\equiv(x^1)^{31}x^6\equiv x^7\mod{31}$

so we have

$\begin{cases}x^5\equiv3\mod{17}\\x^7\equiv3\mod{31}\end{cases}$

Consider the first case. By Fermat's little theorem, we know that

$x^{17}\equiv x^{16}x\equiv x\mod{17}$

so if we were to raise x^5

to the

th power such that

$(x^5)^n\equiv x^{5n}\equiv x\mod{17}$

we would need to choose

such that $5n\equiv1\mod{16}$ (because $16+1\equiv1\mod{16}$ ). We can find such an

by applying the Euclidean algorithm:

16=3(5)+1

$\implies1=16-3(5)$
$\implies16-3(5)\equiv-3(5)\equiv1\mod{16}$

which makes $-3\equiv13\mod{16}$ the inverse of 5 modulo 16, and so n=13

.

Now,

$x^5\equiv3\mod{17}$
$\implies (x^5)^{13}\equiv x^{65}\equiv x\equiv3^{13}\equiv(3^4)^2\times3^4\times3^1\mod{17}$

$3^1\equiv3\mod{17}$
$3^4\equiv81\equiv4(17)+13\equiv13\equiv-4\mod{17}$
$3^8\equiv(3^4)^2\equiv(-4)^2\mod{17}$
$\implies3^{13}\equiv(-4)^2\times(-4)\times3\equiv(-1)\times(-4)\times3\equiv12\mod{17}$

Similarly, we can look for

such that $7m\equiv1\mod{30}$ . Apply the Euclidean algorithm:

30=4(7)+2

$\implies1=7-3(2)=7-3(30-4(7))=13(7)-3(30)$
$\implies13(7)-3(30)\equiv13(7)equiv1\mod{30}$

so that m=13

is also the inverse of 7 modulo 30.

And similarly,

$x^7\equiv3\mod{31}[/ex] [tex]\implies (x^7)^{13}\equiv3^{13}\mod{31}$

Decomposing the power of 3 in a similar fashion, we have

$3^{13}\equiv(3^3)^4\times3\mod{31}$

$3\equiv3\mod{31}$
$3^3\equiv27\equiv-4\mod{31}$
$\implies3^{13}\equiv(-4)^4\times3\equiv256\times3\equiv(8(31)+8)\times3\equiv24\mod{31}$

So we have two linear congruences,

$\begin{cases}x\equiv12\mod{17}\\x\equiv24\mod{31}\end{cases}$

and because $\mathrm{gcd}\,(17,31)=1$ , we can use the Chinese remainder theorem to solve for

.

Suppose x=31+17

. Then modulo 17, we have

$x\equiv31\equiv14\mod{17}$

but we want to obtain $x\equiv12\mod{17}$ . So let's assume x=31y+17

, so that modulo 17 this reduces to

$x\equiv31y+17\equiv14y\equiv1\mod{17}$

Using the Euclidean algorithm:

17=1(14)+3

$\implies1=3-2=5(3)-14=5(17)-6(14)$
$\implies-6(14)\equiv11(14)\equiv1\mod{17}$

we find that y=11

is the inverse of 14 modulo 17, and so multiplying by 12, we guarantee that we are left with 12 modulo 17:

$x\equiv31(11)(12)+17\equiv12\mod{17}$

To satisfy the second condition that $x\equiv24\mod{31}$ , taking

modulo 31 gives

$x\equiv31(11)(12)+17\equiv17\mod{31}$

To get this remainder to be 24, we first multiply by the inverse of 17 modulo 31, then multiply by 24. So let's find

such that $17z\equiv1\mod{31}$ . Euclidean algorithm:

31=1(17)+14

and so on - we've already done this. So z=11

is the inverse of 17 modulo 31. Now, we take

$x\equiv31(11)(12)+17(11)(24)\equiv24\mod{31}$

as required. This means the congruence $x^{37}\equiv3\mod{527}$ is satisfied by

x=31(11)(12)+17(11)(24)=8580

We want $0\le x$ , so just subtract as many multples of 527 from 8580 until this occurs.

$8580=16(527)+148\implies x=148$

Answer from: Quest

i dont know it

step-by-step explanation:

Answer from: Quest

step-by-step explanation:

to find the amount of gift bags to use all the supplies, find the gcf or greatest common factor. this is the largest number which multiplies evenly into each term.

48 has factors: 1, 2, 3, 4, 6, 8, 12. 16, 24, 48

80 has factors: 1, 2, 4, 5, 8, 10, 16, 20, 40, 80

64 has factors: 1, 2, 4, 8, 8, 16, 32, 64

the highest number factor they all share in common is 8. this means there will be 8 bags with 6 pencils, 10 markers, and 8 stickers in each bag.

Another question on Mathematics

Mathematics, 21.06.2019 17:30

(least common multiples) the answer that i had in the 1st step was lcm of airline tickets sold=72. idk if that even matters but just in case. ! three co-workers are busy selling airline tickets over the phone. in an 8-hour day, charles can sell 8 airline tickets, ann can sell 9 airline tickets, and michelle can sell 6 airline tickets. step 2 of 2: what is the smallest number of 8-hour days needed for each of them to achieve the same number of sales? it takes charles . it takes . it takes .

Answers: 1

Answer

Mathematics, 21.06.2019 23:00

Siri can type 90 words in 40 minutes about how many words would you expect her to type in 10 minutes at this rate

Answers: 1

Answer

Mathematics, 22.06.2019 01:20

Which of the following shows the graph of y=2e^x?

Answers: 2

Answer

Mathematics, 22.06.2019 01:30

Solve for the equation x. 2x + 22 = 4(x + 3)