Wikipedia:Reference desk/Archives/Mathematics/2025 January 31

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 31

Why does this algorithm always lead to the trivial square root of y when y is a perfect square?

This is based on Talk:Kunerth's algorithm#Taking The Square Root of 67*Y Mod RSA260
First take $digitsConstant$, a random semiprime… then use the following pseudocode :

2. Compute : $bb=([[digitsConstant^{0.5}]]+1)^{2}-digitsConstant$
3. Find integers $x$ and $y$ such as (25²+ x×digitsConstant)÷(y×67) = digitsConstant+bb
4. take $z$, an unknown variable, then expand ((67z + 25)²+ x×digitsConstant)÷(y×67) and then take the last Integer part without a $z$ called $w$. $w$ will always be a perfect square.
5. $w=sqrt(w)$
6. Find $a$ and $b$ such as a== w (25 + w×b)
7. Solve 0=a²×x²+(2a×b−(x×digitsConstant))×z+(b²−67×y)
8. For each of the 2 possible integer solution, compute z mod digitsConstant.

The fact the result will be a modular square root is expected, but then why if the $y$ computed at step 2 is a perfect square, z mod\ digitsConstant will always be the same as the Integer square root of $y$ and not the other possible modular square ? (that is, the trivial solution). 2A01:E0A:401:A7C0:9CB:33F3:E8EB:8A5D (talk) 09:22, 31 January 2025 (UTC)

Numbers m such that there is n such that eulerphi(eulerphi(n)) = m but there is no number with exactly m primitive roots

56 is in the range of eulerphi(eulerphi(n)), but there is no number with exactly 56 primitive roots, the numbers like 56 seems to be rare, what is the set of such numbers (i.e. the intersection of (sequence A378508 in the OEIS) and (sequence A231773 in the OEIS)) <= 10000? 220.132.216.52 (talk) 17:16, 31 January 2025 (UTC)