Redirected
retagged by
1,285 views
3 votes
3 votes

Let $m$ and $n$ be two positive integers. Which of the following is NOT always true?

  1. If $m$ and $n$ are co-prime, there exist integers $a$ and $b$ such that $am + bn=1$
  2. $m^{n-1} \equiv 1 (\text{ mod } n)$
  3. The rational number $\frac{n}{m} \cdot \frac{n-1}{m-1} \cdot \frac{n-2}{m-2} \dots \frac{n-(m-2)}{m-(m-2)} \cdot \frac{n-(m-1)}{m-(m-1)}$ is an integer
  4. $m+1$ is a factor of $m^{n(n+1)}-1$
  5. If $2^n -1$ is prime, then $n$ is prime
retagged by

2 Answers

5 votes
5 votes
$m^{n-1}=1(mod \space n)$ is not always true

Consider $m$ and $n$ are not co-primes. Then this result will not hold.

For example, $m=9,n=3$

$9^{3-1} \mod \space 3 \neq 1$
edited by
3 votes
3 votes

if $m$ and $n$ are positive integers ,it means $m=\left\{1,2,3,4,.......\right\}$ and $n=\left\{1,2,3,4,............\right\}$

$A)$ If $m$ and $n$ are co-prime, there exist integers $a$ and $b$ such that $am + bn=1$

Lets take $m=1,n=3$

$\implies am+bn=1$ 

$\implies a+3b=1$

take $a=-2,b=1$

$\implies -2+3=1$

$\implies 1 = 1$

So, this is true.

Proof:

 

$B)$ $m^{n-1}=1$ $mod$ $n$

Lets take some values$:m=1,n=1$

$\implies1^{1-1}=1$ $mod$ $1$$\implies 1^{0}=0$

$\implies 1=0$ $($ False because  $1\neq 0)$

I took a counterexample and proved that the given statement is false.

So, this is false.

$C)$ The rational number $\frac{n}{m} \cdot \frac{n-1}{m-1} \cdot \frac{n-2}{m-2} \dots \frac{n-(m-2)}{m-(m-2)} \cdot \frac{n-(m-1)}{m-(m-1)}$ is an integer

We can prove this one using proof by contradiction.

Let us assume The rational number $\frac{n}{m} \cdot \frac{n-1}{m-1} \cdot \frac{n-2}{m-2} \dots \frac{n-(m-2)}{m-(m-2)} \cdot \frac{n-(m-1)}{m-(m-1)}$ is not a integer.

lets take $m=4,n=8$

$\implies\frac{8}{4} \cdot \frac{8-1}{4-1} \cdot \frac{8-2}{4-2} \dots \frac{8-(4-2)}{4-(4-2)} \cdot \frac{8-(4-1)}{4-(4-1)}$

$\implies\frac{2}{1}\cdot \frac{7}{3}\cdot \frac{6}{2} \cdot \frac{5}{1}=70$ It is a integer.

Here our assumption is false.

So, the given statement is true.

$D)\ m+1$ is a factor of $m^{n(n+1)}-1$

We can prove this using proof by contradiction.

Let us assume $\ m+1$ is  not a factor of $m^{n(n+1)}-1$

Take $m=3,n=2$

$3+1$ is a factor of $3^{2(2+1)}-1$

$4$ is a factor of $3^{6}-1$

$4$ is a factor of $729-1$

$4$ is a factor of $728$

Factor of $728:1,2,4,7,8,13,14,26,28,52,56,91,104,182,364,728$

Here our assumption is false.

So, the given statement is true.

$E)$ If $2^{n}-1$ is prime ,then $n$ is prime

Lets take an example$:n(Prime)=2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,...........$

$P_{n}=2^{n}-1\rightarrow(1)$

Put value one by one and observe the output,

  •     $P_{2}=2^{2}-1=4-1=3\text{(Prime)}$
  •     $P_{3}=2^{3}-1=8-1=7\text{(Prime)}$
  •     $P_{5}=2^{5}-1=32-1=31\text{(Prime)}$
  •     $P_{7}=2^{7}-1=128-1=127\text{(Prime)}$
  •     $P_{11}=2^{11}-1=2048-1=2047=23\times 89{\color{Magenta}{\text{(Not Prime)}} }$
  •     $P_{13}=2^{13}-1=8192-1=8191\text{(Prime)}$

$\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots$

$\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots$

For this one $P_{11}=2^{11}-1=2048-1=2047=23\times 89{\color{Magenta}{\text{(Not Prime)}} }$

If $2^{11}-1$ is prime then $11$ is prime.

we can write like this 

$2^{11}-1$ is prime $\implies 11$ is prime.

$\text{False}\implies\text{anything}\equiv \text{True}$

Proof: 

So, this is true.

(Reference:https://brilliant.org/wiki/mersenne-prime/)

So, the correct answer is $(B).$

edited by
Answer:

Related questions

5 votes
5 votes
2 answers
1
Arjun asked Dec 18, 2018
1,467 views
How many proper divisors (that is, divisors other than $1$ or $7200$) does $7200$ have ?$18$$20$$52$$54$$60$
12 votes
12 votes
2 answers
2
Arjun asked Dec 18, 2018
1,316 views
What are the last two digits of $1! + 2! + \dots +100!$?$00$$13$$30$$33$$73$
1 votes
1 votes
1 answer
3