[Math] How to use the ‘modulus’ operator

contest-mathelementary-number-theorynumber theory

This is a problem from BdMO $2012$ Dhaka region Question Paper:

The product of a number with itself is called its square. For example,
$2$ multiplied by $2$ is $4$, so $4$ is the square of $2$. If you take a square
number and multiply it with itself, what will be the largest possible
remainder if the product is divided by $10$?

I came up with this: $$x^4 \mod {10}$$

I know that the modulus (%) operator calculates the remainder of a division. And that it can be used to see, suppose, whether $N$ is a multiple of $M$ or not. Nothing more than that. I am much familiar with mod because of my programming experience with mid-level languages like C and C++. It was not until later that I came to know that modulus is used in mathematics as well.

Now, how to use the 'modulus' operator? How can I use this to go further into solving this problem?

Best Answer

$1$. The remainder will be the unit digit of the number you are dividing. For example, Remainder when $16$ is divided by $10$ is $6$.

Proof: If you have got a $n$ digit number then you can write it as $10^{n-1}a_0+10^{n-2}a_1+........+10a_{n-2}+a_{n-1}$ where $a_{n-1}$ is the unit digit. Notice that all the terms in the sum are divisible by $10$, the only suspect is $a_{n-1}$.

$2$. Notice that unit digit of a square number can be $0,1,4,5,6,9$ and corresponding unit digits of $4th$ powers can be $0,1,6,5,6,1,$.

So, largest remainder is $6$.

Related Solutions

[Math] How to find modulus square root

An algorithm to compute $\sqrt{c} \pmod {p^2}$ from $\sqrt{c} \pmod {p}$ is given below. It is a simplified version of Alg 2.3.11 (Hensel lifting) from Crandall/Pomerance: Prime Numbers, A Computational Perspective, 2nd ed., 2005 using their notation with $f(x)=c-x^2,\,$ $f'(x)=-2x.$ I include the values for $p=17, c=13$ with the root $r\equiv \sqrt{13} \equiv 8 \pmod {17}$

1.  r = sqrt(c) mod p         = 8
2.  z = (2r)^(-1) mod p       = 16
3.  x = (c-r^2)/p mod p       = -3 = 14
4.  y = x*z mod p             = 14*16 = 3
5.  r = (r + y*p) mod p^2     = 8 + 3*17 = 59

Check: $59^2 \equiv 3481 \equiv 13 \pmod {289}$

And with some larger values using $p=10000000019, c=5:$

1. r = 8068369918
2. z = 8806837007
3. x = 3490140718
4. y = 6519460323
5. r = 65194603361938116055

See also the section Powers of odd primes of John Cook's Solving quadratic congruences and the already cited Wikipedia section from my comment (using $p=7, c=2$).

[Math] How to solve a problem using the Chinese remainder theorem and how does mod operator is understood correctly

The $\textrm{mod}$ notation is not an operator that gives you a single output.

Don't read it as if it was computer code. I would only read the $\textrm{mod}$ notation in English. $\text{mod}\;n$ means the preceding equation/formula is under modulus $n$. In the context of integer numbers, we consider each integer number by its Euclidean remainder when divided by $n$.

$\equiv$ is a notation for equivalence relations. Please read its introductions on the internet.

For example, we say 13 is equivalent (or congruent, some even say equal, depending on the context) to 23 modulus 10, denoted by $13\equiv23\;\textrm{mod}\;10$ because they have the same remainder when divided by 10, which is 3. Negative number is usually read "in reverse". For example, $13\equiv-7\;\textrm{mod}\;10$.

As for your puzzle at the beginning, you don't have to use Chinese Remainder Theorem. I think Chinese Remainder Theorem is a bit of a leap when you are just learning the mod notation. Try solving the puzzle yourself without the theorem and share where you are first.

Best Answer

Related Solutions

[Math] How to find modulus square root

[Math] How to solve a problem using the Chinese remainder theorem and how does mod operator is understood correctly

Related Question