0
$\begingroup$

This problem is identified while solving one of the unsolved problem exist currently.

Problem name : Ghandhan Problem M and N are integer and should satisfy following conditions. 1. M > N 2. M is not Divisible by N (Remainder not 0) 3. M*M is divisible by N. (Remainder is 0) 4. M and N are odd numbers. 5. N is not a multiple of any Square number except 1(Because all numbers are multiple by 1 and 1 is square number) .

There are solutions for below combinations. A) M and N are even numbers M = 6 , N = 4 M = 12, N = 8 i.e. N multiples of 4 whereas M multiples of 6. (4 is square number) B)M is even number and N is odd number M = 12, N = 9 M = 24, N = 18 i.e.N multiples of 9 whereas M multiples of 12. (9 is square number). C) M and N are odd number M = 15, N = 9 i.e. N is multiples of any square number (multiples of 3*3 here)

But need solution for odd number for both M and N with 5 conditions mentioned above ? Also need confirmation whether there are finite number of solutions exist for the same?

(This is already asked on openproblemgarden and mathoverflow.net)

$\endgroup$
  • $\begingroup$ Welcome to MSE! It helps readability to format questions using MathJax (see FAQ). Regards $\endgroup$ – Amzoti Apr 7 '13 at 5:02
  • 1
    $\begingroup$ Going to MO with this was a mistake IMHO. They will tell you why. $\endgroup$ – Jyrki Lahtonen Apr 7 '13 at 5:52
3
$\begingroup$

First of all, there is no integer satisfying condition 5, since $1$ is a square number, and every integer is a multiple of $1$. So I'll make believe condition 5 is that $n$ is not a multiple of any square greater than $1$.

In that case, the Unique Factorization Theorem is easily seen to imply that if $n$ divides $m^2$ then $n$ divides $m$.

EDIT: It appears I have not explained myself to the satisfaction of OP, so I will elaborate.

Assume condition 5. Let $p$ be a prime dividing $n$. Then $p^2$ doesn't divide $n$. Thus, $n$ is a product of distinct primes --- we may write $$n=p_1p_2\times\cdots\times p_r$$ for some $r$ and some distinct primes $p_1,p_2,\dots,p_r$.

Now assume in addition condition 3. Let $p$ be a prime dividing $n$. Then $p$ divides $m^2$. But if a prime divides a product of two numbers, then it divides (at least) one of the numbers. (This requires proof, and is one of the main steps on the way to the usual proof of UFT, but I'll just refer OP to any intro number theory text for this). So, $p$ divides $m$. That is, every prime dividing $n$ also divides $m$. It follows that $p_1p_2\times\cdots\times p_r$ divides $m$, which is to say, $n$ divides $m$. But this contradicts condition 2.

So we have proved that it is impossible for conditions 2, 3, and 5 to hold simultaneously.

$\endgroup$
  • $\begingroup$ Thanks Myerson for sharing answer. As per you Unique Factorization Theorem is easily seen to imply that if n divides m2 then n divides m.. Then i have proof that 'Unique Factorization theorem' fails for the below 3 category of examples.A) M and N are even numbers M = 6 , N = 4 M = 12, N = 8 i.e. N multiples of 4 whereas M multiples of 6. (4 is square number) B)M is even number and N is odd number M = 12, N = 9 M = 24, N = 18 i.e.N multiples of 9 whereas M multiples of 12. (9 is square number). C) M and N are odd number M = 15, N = 9 i.e. N is multiples of any square number (multiples of 3*3). $\endgroup$ – VENKATESH KRISHNARAM Apr 7 '13 at 6:12
  • $\begingroup$ Thanks Lahtonen. I have given 3 Category of examples that we have solution only for these 3 Category. But with the 5 conditions i have mentioned above there are no solutions exist as of now which i tried. Please note that the examples i have provided is not solution of my problem. I just want proof either solution exist for my 5 condition (or) proof that there is no solution for this 5 condition. $\endgroup$ – VENKATESH KRISHNARAM Apr 7 '13 at 6:47
  • $\begingroup$ There is no solution for the five conditions. If $n$ is not a multiple of any square greater than $1$, and $n$ divides $m^2$, then, as I wrote, it follows from UFT that $n$ divides $m$. $\endgroup$ – Gerry Myerson Apr 7 '13 at 9:04
  • $\begingroup$ Thanks Myerson. You are referencing the UFT and saing if n divides square(m) then n divides m. But i have example where it is not satisfying. When there is possible solution against UFT there may be solution for my 5 conditions also. Please let me know the solution or proof that it does not exist. $\endgroup$ – VENKATESH KRISHNARAM Apr 7 '13 at 12:16
  • $\begingroup$ Also there are no statement in the UFT which you have mentioned. Please suggest by looking the theorem statement. $\endgroup$ – VENKATESH KRISHNARAM Apr 7 '13 at 12:18
0
$\begingroup$

No solutions exist. $\rm(5)\:\Rightarrow\:n\:$ is not divisible by the square of any prime, so the unique prime factorization of $\rm\:n\:$ is a product of distinct primes $\rm\:n = p_1\cdots p_k.\:$ Now $\rm\:n\mid m^2\:\Rightarrow\:nk = m^2.\:$ Comparing the unique prime factorizations of both sides of $\rm\:nk = m^2\,$ shows that each prime $\rm\:p_i\:$ must occur to power $\ge 1\,$ in $\rm\:m,\:$ hence $\rm\:n\mid m,\:$ contra hypothesis $(2)$.

Remark $\ $ An integer $\rm\:q\ne 0\:$ without any square factors (except $1$) is called squarefree. Below are various equivalent characterizations of $ $ "$\rm q\,$ is a squarefree integer" (for proofs see here). Your equations have no solution because they assume both $(1)$ and not $(3)\,$ from the list below, i.e. they assume one notion of squarefree, and the negation of an equivalent notion of squarefree. Knowledge of these equivalent characterizations proves very useful in number theory (for many other purposes besides avoiding contradictions).

Theorem $\ $ Let $\rm\ 0 \ne q\in \mathbb Z\:.\ $ The following are equivalent.

$(1)\rm\quad\:\ \ n^2\ |\ q\ \Rightarrow\ n\ |\ 1\qquad\qquad\!$ for all $\rm\ n\in \mathbb Z $

$(2)\rm\quad\:\ \ n^2\ |\ q\:m^2 \Rightarrow\ n\ |\ m\qquad\ $ for all $\rm\:\ n,m\in \mathbb Z$

$(3)\rm\qquad\ q\ |\ n^2\ \Rightarrow\ q\ |\ n\qquad\quad\ $ for all $\rm\:\ n\in \mathbb Z $

$(4)\rm\qquad\ q\ |\ n^k\ \Rightarrow\ q\ |\ n\qquad\quad\ $ for all $\rm\:\ n\in \mathbb Z\:,\ k\in \mathbb N $

$(5)\rm\quad\:\ \: q^q\ |\ n^n\ \Rightarrow\ q\ |\ n\qquad\quad\ $ for all $\rm\:\ n\in \mathbb N\:,\ $ for $\rm\ q > 0 $

$\endgroup$
  • $\begingroup$ Thanks Math Gems. I agree with this. This statment will be useful for me to resolve the problem in which i am working. $\endgroup$ – VENKATESH KRISHNARAM Apr 19 '13 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.