Division of prime numbers

149 Views Asked by At

a) Let p and q be different odd primes. Is there any such numbers for which $$(p-1)(q-1) \mid (pq)^2 +3$$?

b) Let q be an odd prime number. Is there any q for which $$6(q-1) \mid 81q^2 + 3$$?

(I expect the answer for both to be no) (q does not equal 3)

These are small chunks from a number theory problem that left me to solve and I'll be done with the problem. Can someone please help? The original problem is from a regional Bulgarian competition.

3

There are 3 best solutions below

1
On

$p=3$,$q=7$ for $a$ and $q=3$ for $b$) since $(3-1)(7-1)=12$ which divides $(3·7)^2+3=444$ and $6(3-1)=12|(81·3^2)+3=732$

0
On

b) requires $q-1|81q^2+3= 81(q-1+1)^2+3=\lambda (q-1)+84$, so $q-1|84$ And since q is odd and $81q^2+3=4(\mod 8)$, $q-1=2(\mod 4)$ so $q-1 \in \{2, 6, 14, 42\}$, or $q \in \{3,7,43\}$ We could verify only 3 is valid.

8
On

If both p and q are larger than 3, it is obvious that both p-1 and q-1 is not multiple of 3.

And since $(pq)^2+3=4(\mod 8)$, both $m=\frac{p-1}2$ and $n=\frac{q-1}2$ are odd number.

Since $m| p^2q^2+3$, -3 is quadratic residue of m so that $m=1(\mod 6)$ which means $p=3(\mod 6)$ and it is invalid since p should be prime more than 3.