On my homework it says $\sqrt{48}\pmod{73}$ but I have in my notes that $\sqrt{y\pmod{p}}\equiv y^{(p+1)/4}\mod{p}$. Which I feel like I should use. When I type it as it appears on the homework into wolfram alpha it says $4 \sqrt{3}$ is the answer. The hint is to use a table of $15^n\pmod{73}$. I am thoroughly confused. Please help.
Asked
Active
Viewed 239 times
1
-
4The formula you cite is only valid when $p\equiv3\pmod 4$. – Angina Seng Feb 23 '19 at 18:32
-
For numbers this small, you really should be able to do it by hand (it helps to notice that $73+48=121$). But for larger numbers, wolfram alpha works fine. Just as it to solve $x^2=48$ mod $73$, or such. – lulu Feb 23 '19 at 18:35
-
@lulu I was thinking this, something like x^2 = 48 mod 73 which would make the answer 11? – Christheyankee Feb 23 '19 at 18:40
-
Hint: $\bmod 73!:,\ 48\equiv 48!+!73 = 121\ \ $ – Bill Dubuque Feb 23 '19 at 18:42
-
Well, $\pm 11$, which you might also want to write as $x\equiv 11,62 \pmod {73}$ – lulu Feb 23 '19 at 18:42
-
okay thnx any idea about the purpose of the hint? @lulu – Christheyankee Feb 23 '19 at 18:44
-
1Well.. It happens that $15$ is a primitive root $\pmod {73}$ which is why you are able to solve the problem using the table of powers of $15$. But that seems artificial. Perhaps, in the context of this problem, the writers had already sorted out that $15$ was a primitive root and worked out its powers? in any case, if you happen to have that table, you could remark that $15^{26}\equiv 48\pmod {73}$, whence $15^{13}\equiv 62\pmod {73}$ is a square root of $48$. – lulu Feb 23 '19 at 18:45
-
Did a prior exercise construct a table of powers of $15$? – Bill Dubuque Feb 23 '19 at 18:47
-
Yeah maybe, we were just given the table for no apparent reason. How would you solve the problem with the table? @lulu – Christheyankee Feb 23 '19 at 18:49
-
@BillDubuque lol this is exercise one, im stupid. – Christheyankee Feb 23 '19 at 18:50
-
I edited my last comment to explain how to use that table. – lulu Feb 23 '19 at 18:50
-
Then I presume your are expected to construct the table. You'll get $\large ,48\equiv 15^{\large 2N}!\equiv (15^{\large N})^2$ presuming $\large 15$ is a primitive root (which it is since $\large 15^{\large 72/p}!\not\equiv 1,$ for all the prime factors $,p=2,3,$ of $72$) – Bill Dubuque Feb 23 '19 at 18:56
-
You'll find $,N = 13,$ so a square root of $48$ is $\large ,15^{13}\equiv 62\equiv -11,,$ hence so to is its negative $11\ \ $ – Bill Dubuque Feb 23 '19 at 19:05
-
Can you explain the part about a square root of 48 is 15^13? @BillDubuque – Christheyankee Feb 23 '19 at 19:14
-
See my prior two comments. – Bill Dubuque Feb 23 '19 at 19:16
-
Oh lol thnx I missed the top comment – Christheyankee Feb 23 '19 at 19:18
3 Answers
2
$x\equiv \sqrt{48}\pmod{73}\iff x^2\equiv 48\pmod{73}$
This is the way you should see it.
Since $48 = 16\times 3= 4^2\times 3$
Then $x$ should be of the form $x=4y$ where $y^2\equiv 3\pmod{73}$
By extended Euclidean algorithm $3^{-1}\equiv 49\pmod{73}$
Thus $(3\times 7)^2\equiv (3\times 49)\times 3\equiv 1\times 3\equiv 3\pmod{73}$
Finally $x=4\times 21=84\equiv 11\pmod{73}$
Giving the result $$\sqrt{48}\equiv 11\pmod{73}$$
Rem: the other value being $-11\equiv 62\pmod{73}$.
zwim
- 28,563
-
We were told to solve it with a table containing powers of 15 mod n, so thinking like this confused me. Comment section helped with that and this how it should normally be solved so will mark this as answer. – Christheyankee Feb 23 '19 at 20:18
-
1@Christheyankee This is certainly not "how it should normally be solved". It was pure luck that $3^{-1}$ happened to be an obvious square. One will rarely be so lucky in general. There are alorithms for modular square-roots but the point of the exercise is not that. Rather, it's to help you understand how to compute the roots using the cyclic group structure. This is sometimes expressed using an analog of logs and called "index arithmetic", e.g. see here. – Bill Dubuque Feb 23 '19 at 21:07
-
I agree with that. The fact about $49$ is about as lucky as $48+73=121=11^2$. But the diversity of methods is what makes MSE great. The method about powers of $15$ has been exposed in the comment section, so I let @Bill the privilege to make it a full answer or let it as is. – zwim Feb 23 '19 at 21:17
0
Observe that $\;48=4^2\cdot 3\;$ , and since $\;73=1\pmod 4\;$ then
$$\binom 3{73}=\binom{73}3=\binom13=1$$
then $\;48\;$ is the product of two squares modulo $\;73\;$ and thus it iself is one of these.
DonAntonio
- 211,718
- 17
- 136
- 287
-
1How does this use the 15^n table I can't figure that part out still @DonAntonio – Christheyankee Feb 23 '19 at 18:39
-
0
Presumably if you have the table, then it renders $15^{26}\equiv 48$. So you get a square root by taking half that even exponent, thus $15^{13}\equiv ... $. Don't forget the additive inverse is a square root, too.
Oscar Lanzi
- 39,403