How to solve $x^x \equiv 0 \pmod y$ Given a constant y, I am trying to find the smallest value for x that satisfies the equation $x^x = 0 \mod y$.  So far I have been able to determine that $x$ is equal to the product of all the prime factors of y multiplied by $2^a$, where a is integer equal or greater than zero.
For example when $y = 420$, the prime factors of y are $2,3,5$, and $7$ so $x = 2^a \cdot 2 \cdot 3  \cdot 5 \cdot 7$ so $x = 210$. More often than not a =0, but not always.
I am working with very large numbers, and performance is important so I need a way of calculating x without working out the prime factors.
 A: Unfortunately there won't be an easy way to solve this for huge numbers $y$. If you could quickly answer this question then for any $y \in \mathbb{N}$ you'd immediately be able to tell whether $y$ is squarefree by checking whether $x = y$. But to quote from that Wolfram article: "There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer. In fact, this problem may be no easier than the general problem of integer factorization."
Here's a proof that $x = y$ if and only if $y$ is squarefree. First direction: If $p | y$ for some prime $p$ then we must have $p | x$ too, so if $y$ is squarefree then we get $x \ge y$. Clearly $y$ is a solution of the original equation, and $x$ is defined as the smallest positive integer solution, so $x = y$.
For the second direction: Assume $y$ is NOT squarefree. Write the prime factorization of $y$ as $\prod_{j=1}^n p_j^{e_j}$ where we assume $e_1 > 1$. Define $z = \frac{y}{p_1}$; then $z < y$, and we claim $z^z \equiv 0 \mod y$. To show $y | z$, we need to show $p_j^{e_j} | z^z$ for all $j$. For $j \ge 2$ this is obvious, since $p_j^{e_j} | z | z^z$. For $j = 1$ we have $p_1^{e_1-1} | z$, so $p_1^{(e_1-1)z} | z^z$. We also know $(e_1-1)z \ge e_1$ because $z > 1$ and $e_1 \ge 2$, so we conclude $p_1^{e_1} | z^z$ and thus $z$ is a solution of the congruence. Therefore we must have $x < y$ since $x$ is the smallest positive solution.

To solve the problem for cases where we know the factorization of $y$: Write $y = \prod_{j=1}^n p_j^{e_j}$. Let $s$ be the squarefree part of $y$, i.e. $s = \prod_{j=1}^n p_j$. Let $m = \max_j \left \lceil \frac{e_j}{s} \right \rceil$ where $\lceil \, \rceil$ is the ceiling function. Then $x = ms$ will be the smallest positive solution you're looking for. (Do you see why?)
So, it turns out that your conjectures were mostly quite accurate. We do always have $s | x$, and we'll have $s = x$ in most cases - basically unless $y$ is very heavily made up of powers of a single prime. However, your conjecture about the multiplier being a power of 2 is not true in general. To give an explicit counterexample: Let $y = 64 = 2^6$. Then the formula above (or just testing by hand) shows that the correct minimal solution is $x = 6$, which is not of your conjectured form $2 \cdot 2^a$.
