Find the modular residue of this product..

Question

Please help me solve this and please tell me how to do it..

$12345234 \times 23123345 \pmod {31} = $?

edit: please show me how to do it on a calculator not a computer thanks:)

Answer 1

We want to replace these big numbers by much smaller ones that have the same remainder on division by $31$.

Take your first big number $12345234$. Divide by $31$ with the calculator. My display reads $398233.3548$. Subtract $398233$. My calculator shows $0.354838$. Multiply by $31$. The calculator gives $10.999978$. If it were perfect, it would say $11$.

Do the same with the other big number. My calculator again says $10.99978$, and if perfect would say $11$.

Multiply $11$ by $11$, and find the remainder when $121$ is divided by $31$. Again, we could use the calculator. But it can be done in one's head. The remainder when we divide by $31$ is $28$.

Remark: It can be fairly important not to write down an intermediate calculator result, and rekey. The reason is that the calculator inernally keeps guard digits, that is, it is calculating to greater precision than it displays. If you rekey, typing in only digits that you see, you will lose some of the built-in accuracy that you paid for. For similar reasons, it is useful to learn to make use of the memory features of your calculator.

Let's ee why the procedure we used works. When we divide $12345234$ by $31$, the stuff before the decimal point is the quotient. The remainder is unfortunately not given directly, but what's "left over" is (approximately) $0.354838$. This is a decimal representation of $\frac{r}{31}$, where $r$ is the (integer) remainder. To recover $r$, we multiply $0.354838$ by $31$. Because of internal roundoff, we usually don't get an integer, but most of the time, if the divisor (here $31$) is not too large, we get an answer that is very close to an integer, so we can quickly decide what $r$ must be.

Answer 2

As $10^1\equiv 10\pmod{31},$

$10^2=100\equiv7,$

$10^3\equiv10\cdot7\equiv8,$

$10^4\equiv49\equiv18,$

$10^5=10^2\cdot10^3\equiv 7\cdot8\equiv25,$

$10^6=(10^3)^2\equiv8^2\equiv2,$

$10^7=10^4\cdot10^3\equiv18\cdot8\equiv20,$

$$12345234=4+3\cdot10+2\cdot10^2+5\cdot10^3+4\cdot10^4+3\cdot10^5+2\cdot10^6+1\cdot10^7$$ $$\equiv4+3\cdot10+2\cdot7+5\cdot8+4\cdot18+3\cdot25+2\cdot2+1\cdot20\pmod{31}$$