Show that 101 is a prime number given the fact that 10 squared is 100 and squared of 11 is 121.
Question: Use the fact that $10^2 = 100$ and $11^2 = 121$ to show that the number 101 is a prime number.
Could someone please given me a hint on how to solve this problem. I can't seem to relate $11^2=121$ to the fact that 101 is a prime number. I thought of using theorem of gcd or modular arithmetic, but I don't know where to start.
$\endgroup$ 24 Answers
$\begingroup$Here is one way to use both the facts you were given to start with, assuming that you understand that $11$ is a prime number and the prime factorization of $10$ is $2\cdot 5$.
Since $11^2=121>101$, you know that the product of any set of $2$ or more primes, all of which are $\ge 11$ will be $\ge 121 > 101$, so looking at such sets of prime factors is ruled out.
You (should) also know that for any two consecutive integers $\gcd(n,n+1)=1$. Since $100=10^2=2^2\cdot 5^2$, the primes ($2,5$), being factors of $100$, cannot be factors of $101$.
So if $101$ is composite, it must have at least one prime factor smaller than $11$, but not including $2$ or $5$. The only possible candidates that meet those restrictions are $3$ and $7$. But $3\not \mid 101$ and $7\not \mid 101$. Ergo, $101$ cannot be composite, which means that it is prime.
$\endgroup$ $\begingroup$Well, otherwise it would be divisible by a prime smaller than $10$ which can be easily refuted by hand calculation.
$\endgroup$ $\begingroup$Observe, with the positive square root taken, that for $n, \lambda,\mu\in \Bbb R^+$, that:
$$(\sqrt{n}+\lambda)(\sqrt{n}+\mu)=n+(\lambda+\mu)\sqrt n +\lambda\mu>n$$
On the contrary:$$(\sqrt{n}+\lambda)(\sqrt{n}-\mu)=n+(\lambda-\mu)\sqrt n-\lambda\mu$$is not always $>n$. We have equality when $\mu=\frac{\lambda\sqrt n}{\lambda +\sqrt n}$
In other words, the factor pairs of any composite number always include a number that is at most the square root of that number. Listing factors will help you see this.
For example, for $n=48, \sqrt{n}\approx 6.92$ (All that matters is that $6<\sqrt{48}<7$). Then, the factor pairs are:$$1\cdot 48$$$$2\cdot 24$$$$3 \cdot 16$$$$4\cdot 12$$$$6\cdot 8$$The smaller number on the left is never greater than $\sqrt {48}\approx 6.92$
You've been told in your question that $10<\sqrt{101}<11$. This means that if $101$ has any factor pairs, the smallest in a given pair is at most $10$.
$\endgroup$ $\begingroup$If $101 = m*n$ then we can't have $m= n$. (why not?[1])
If we assume $m < n$ then $m \le 10$. (why?[2])
And if $101$ is not prime then it has a prime factor $p \le m \le 10$. (why?[3])
So find it. Check every prime $p \le 10$ and see if $p|101$. If none do, then $101$ is prime. (why?[4])
The only primes $p \le 10$ are $2,3,5,7$. So check if those divide $101$. If none of them do, then $101$ is prime.[5]
===
1
If $m = n$ then $101 = m^2$ but $10^2 < 101 < 11^2$ so that would mean $10^2 < m^2 < 11^2$ so $10 < m < 11$ but there is no such integer.
2
If $mn = 101$ then $n = \frac {101}m$. If $m > 10$ then $n =\frac {101}{m}< \frac {101}{10} =10.1$ so $n \le 10$ and $n < m$. That's a contradiction. If $mn =101$ and $m < n$ then $m \le 10$ and $n =\frac {101}m \ge \frac{101}{10} 10.1$ so $m \le 10$ and $n \ge 11$.
3
If $m|101$ then $m$ has a prime factor less or equal to it. And as $m \le 10$ there must be a prime $p$ so that $p|m$, $p\le m \le 10$, and if $p|m$ and $m|101$ then $p|101$.
4
If $m$ has no prime divisors, not even itself, then $m =1$ and $101$ has no divisor $\le 10$. But, by 1), if $101$ is composite it must have. Just to reiterate if $101 = m*n$ and $m \ge 11$ and $n \ge 11$ then $101 = m*n \ge 11*11 = 121$ which is a contradiction.
5:
$\endgroup$$2\not \mid 101$ as $2*50 =100 < 101 < 102 = 2*51$. And $3\not \mid 101$ aos $99 = 3*33 < 101 < 102 = 3*34$ and $5\not\mid 101$ because $5*20=100 < 101 < 105 = 5*21$. And $7\not \mid 101$ because $7*14=98 < 101 < 105 = 7*15$.
