User talk:Aadenboy/Self-equaling squares

Looking at things a bit closer, I think I can see a more specific pattern. The amount of self-equaling squares for a base seems to be $2^{\omega (n)}$, where $\omega (n)$ is the number of unique prime factors $n$ has. For example, since $4063620694016=2^{16}\times 13^{5}\times 167$, if the pattern is correct, it should only have $2^{3}=8$ self-equaling squares. I'll probably try to prove this later (a proof probably already exists somewhere but I think it'd be fun to try on my own). –PkmnQ (talk) 09:26, 11 May 2025 (UTC)

that's interesting! I wrote up a quick script to test this hypothesis and it does seem to hold true for the first 30k something numbers

local primes = require("primes") -- long list, highest is 1299827

function factorize(n)
    local hits = {}
    local unique = {}
    local current = n
    ::redo::
    for i=1, #primes do
        local prime = primes[i]
        if current % prime == 0 then
            current = current / prime
            if not hits[i] then table.insert(unique, prime) end
            hits[i] = (hits[i] or 0) + 1
            if current > 1 then goto redo else break end
        end
    end
    return hits, unique
end

for base=2, 100000 do -- arbitrary
    local digits = {}
    local _, target = factorize(base)
    for i=0, base-1 do
        if i^2 % base == i then
            table.insert(digits, i)
        end
    end
    print("Base "..base..": "..(2^#target == #digits and "PASS" or "FAIL")..". "..math.floor(2^#target).." expected, got "..#digits)
    if 2^#target ~= #digits then os.exit() end
end

—aadenboy (talk|contribs) 17:17, 11 May 2025 (UTC)

completely forgot I had the program running in the background, all 100000 passed —aadenboy (talk|contribs) 18:40, 11 May 2025 (UTC)

Alright, I forgot about this for a bit but here's half of the proof I was imagining:

Looking at just prime powers for now, let's take $k$ to be a self-equaling square modulo $p^{n}$ for prime $p$ and positive integer $n$. $k$ can either be divisible by $p$ or not divisible by $p$.

In the case that $k$ is divisible by $p$ (i.e. $k=px$ for some integer $x$), then $k^{n}\equiv (px)^{n}\equiv p^{n}x^{n}\equiv 0x^{n}\equiv 0\ (\mathrm {mod} \ p^{n})$. But $k^{n}\equiv k\ (\mathrm {mod} \ p^{n})$ must also be true, thus $k\equiv 0\ (\mathrm {mod} \ p^{n})$.

For the other case where $k$ is not divisible by $p$, $k$ is necessarily coprime to $p^{n}$. Thus, $k^{\phi (p^{n})}\equiv 1\ (\mathrm {mod} \ p^{n})$ by Euler's totient theorem. As before, since $k^{\phi (p^{n})}\equiv k\ (\mathrm {mod} \ p^{n})$ must also be true, $k\equiv 1\ (\mathrm {mod} \ p^{n})$ follows.

Therefore, every self-equaling square $k$ modulo a prime power $p^{n}$ must be congruent to either $0$ or $1$. Or in other words, $0$ and $1$ are the only self-equaling squares modulo $p^{n}$.

The other half is probably the easier part, some application of the Chinese remainder theorem should work. –PkmnQ (talk) 11:13, 23 May 2025 (UTC)