So here's some I came up with a while back.

As per the above, you can't check the mod of any number over 2251799999999

But there's a workaround in the form of these:

=number-(INT(number/divisor)*divisor)

=MOD(MOD(number,134217728*divisor),divisor)

Here's two that uses those workarounds

=OR(p=3,p=5,AND((p-(INT(p/((ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25))+1))*((ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25))+1)))))

=OR(p=3,p=5,AND(MOD(MOD(p,134217728*((ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25)))),1+((ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25))))))

From memory they handles much larger numbers before Excel runs out of resources than the revision of shrivallabha's formula does. But haven't retested this.

Anyone care to do a comparison on their pcs and post back?