How many $k$ satisfy the equation $(p \cdot k)^2 \equiv 0 \pmod{p^n}$ where $k < p^n$ and $p$ is prime

Question

How many $k$ satisfy the equation $(p \cdot k)^2 \equiv 0 \pmod{p^n}$ where $k < p^n$ and $p$ is prime?

I attach very simple code:

#include <stdio.h>
#include <math.h>

unsigned long long int ipow( unsigned long long int base, unsigned long long int exp )
{
    unsigned long long int result = 1ULL;

    while( exp )
    {
        if ( exp & 1 )
        {
            result *= (unsigned long long int)base;
        }
        exp >>= 1;
        base *= base;
    }

    return result;
}


int main()
{
    long long int p = 3;

    long int j;
    for(j=2; j < 25; j++)
    {

        long long int limit = ipow(p, j);

        long long int count = 0;

        long long int i;
        for(i=0; i < limit; i+=p)
        {
            if( (i*i) % limit == 0 )
                count++;    
        }

        printf("n=%ld count=%lld\n", j, count);

    }

    return 0;
}

For $p=3$ it return:

n=2 count=3
n=3 count=3 
n=4 count=9 
n=5 count=9 
n=6 count=27 
n=7 count=27 
n=8 count=81 
n=9 count=81 
n=10 count=243 
n=11 count=243
n=12 count=729
n=13 count=729
n=14 count=2187
n=15 count=2187
n=16 count=6561
n=17 count=6561
n=18 count=19683
n=19 count=19683
n=20 count=51432
n=21 count=17144
n=22 count=17146

I am interested in the case for very large $n$ (and $p$).

Answer 1

I believe your program is wrong, for example for $p=3$, $n=3$ and $k<3^3$ $$3^3 \mid (3 \cdot 3 \cdot 1)^2$$ $$3^3 \mid (3 \cdot 3 \cdot 2)^2$$ $$...$$ $$3^3 \mid (3 \cdot 3 \cdot 8)^2$$ where $k=3\cdot 8 < 3^3$, so there are $8$ cases, not $3$.

---

Generally (using Euclid lemma) $$p^n \mid p^2 k^2 \Rightarrow p^{n-2} \mid k^2$$ from $p \mid k^2 \Rightarrow p^2 \mid k^2$ we have

• if $n-2$ - even then $p^{n-2}\mid k^2$
• if $n-2$ - odd then $p^{n-2+1}\mid k^2$

which is equivalent to $p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor }\mid k^2$. As a result $$p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \leq k_1^2=p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \cdot 1^2 < p^{2n}$$ $$p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \leq k_2^2=p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \cdot 2^2 < p^{2n}$$ $$...$$ $$p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \leq k_q^2=p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \cdot q^2 < p^{2n}$$ or $$1 \leq 1^2 < p^{2n - 2 \left \lfloor \frac{n-2+1}{2} \right \rfloor }$$ $$1 \leq 2^2 < p^{2n - 2 \left \lfloor \frac{n-2+1}{2} \right \rfloor }$$ $$...$$ $$1 \leq q^2 < p^{2n - 2 \left \lfloor \frac{n-2+1}{2} \right \rfloor }$$ and there are $$p^{n - \left \lfloor \frac{n-2+1}{2} \right \rfloor }-1$$ such $k$'s.

Answer 2

First, your code needs modification to calculate what you need:

        if( (i*i) % limit == 0 )

this should be

        if( (p*p*i*i) % limit == 0 )

(In the following I consider when $n>2$ since when $n=2$ or 1, all $k$ satisfy the condition.)

It should hold for the positive $k$: $k\ge p^{(n-2)/2}$.

And as you can see from this expression, it depends on if $n$ is odd or even .

Even case: the smallest positive $k$ is $p^{(n-2)/2}$, and only

$\{p^{(n-2)/2},2p^{(n-2)/2},3p^{(n-2)/2},\cdots,p^{n}-p^{(n-2)/2}\}$

should satisfy your condition as $k$ except 0. The cardinality of this set including 0 is $p^{(n+2)/2}$.

Odd case: the positive smallest $k$ is $p^{(n-1)/2}$, and only

$\{p^{(n-1)/2},2p^{(n-1)/2},3p^{(n-1)/2},\cdots,p^{n}-p^{(n-1)/2}\}$

should satisfy your condition as $k$ except 0. The cardinality of this set including 0 is $p^{(n+1)/2}$.

You would wonder this is different from what you see from your numerical experiment, but this is just because of the machine precision of long long int.