Complex modulus problem

Number Theory Level 3

Let

${ n }^{ 3a }+k\quad \equiv \delta \pmod { { n }^{ 2 }+n+1}$ .

for natural numbers $a$ , $k$ and $n$ . Find $\delta$ .

0 Impossible to tell n + k n - k + 1 7 k + 1 n - 1 k

2 solutions

Alex G
Aug 4, 2016

Note that $n^{3a}=(n^3)^a$ , so we can evaluate $n^3 \mod n^2+n+1$ and then consider it raised to the a.

Using long division (or synthetic division if it is preferred), we divide $n^3$ by $n^2+n+1$ . The result is $n-1+\dfrac{1}{n^2+n+1}$ . This shows that $n^3 \equiv 1 \mod n^2+n+1$ . Any power of 1 is 1, therefore $n^{3a} \equiv 1 \mod n^2+n+1$ . Adding k to the previous result, the final solution is $\boxed {k+1}$

Kushal Bose
Aug 4, 2016

$n^3a -1 + k+1 \equiv \pmod {n^2+n+1}$

$n^3a-1$ is divisible by both $n=\omega$ and $n=\omega^2$

Then $n^{3a}-1$ is divisible by $n^2 +n+1$

So, remainder is $k+1$

Why is ${ n }^{ 3a }-1$ divisible by $n=\omega$ and $n={ \omega }^{ 2 }$ ?

Ραμών Αδάλια - 4 years, 10 months ago

Any power which is multiple of 3 raised to n=w and n=w^2 will be 1 here w and w^2 are cube roots of unity.

Kushal Bose - 4 years, 10 months ago

Complex modulus problem

2 solutions

0 pending reports