Question

Let $N=2^{1224}-1,\alpha =2^{153}+2^{77}+1$ & $\beta =2^{408}-2^{204}+1$, then the remainders when 'N' is divided by $\alpha$ & $\beta$ are respectively,

• A. $0,0$
• B. $0,1$
• C. $1,0$
• D. $1,1$

Answer 1

Answer: (A)

$0,0$

$2^{1224}-1$
$=(2^{153}{)}^8-1$
$=x^8-1$ ...(say)
$=(x^4-1)(x^4+1)$
$=(x^2-1)(x^2+1)(x^4+1)$
Now
$(x^2+1)$
$=(x+1{)}^2-2x$
$=(2^{153}+1{)}^2-2^{154}$
$=(2^{153}+1{)}^2-(2^{77}{)}^2$
$=[2^{153}+2^{77}+1][2^{153}-2^{77}+1]$
$=\alpha [2^{153}-2^{77}+1]$ ...(i)
$x^4+1$
$=2^{612}+1$
$=(2^{204}{)}^3+1$
$=(2^{204}+1)(2^{408}-2^{204}+1)$
$=(2^{204}+1)\beta$
Thus
$2^{1224}-1=\alpha [2^{153}-2^{77}+1]\left(\right(2^{153}{)}^2-1\left)\right(2^{204}+1)\beta$
Hence the remainders will be zero.