Note: that this is not precisely the same as  that has been asked before.  Let $n$ be the largest integer. Then $n&gt;1$. Now $n^2$ is also an integer, and $n^2&gt;n.1=n$. So $n^2&gt;n$. which contradicts $n$ being the largest integer. Therefore our initial assumption is false, and 1 is the largest integer, as claimed.
112159
Let $n$ be the largest positive integer. Since $n ≥ 1$, multiplying both sides by $n$ implies that $n^2 ≥ n$. But since $n$ is the biggest positive integer, it is also true that $n^2 ≤ n$. It follows that $n^2 = n$. Dividing both sides by $n$ implies that $n = 1$.  The goal is to find the flaw in the reasoning of the proof rather than find a proof that proves it wrong. Here's where I think the problem is:  It was stated that $n^2 ≥ n$ after multiplying both sides of the inequality by $n$. But then because $n$ is the largest possible integer, $n^2 ≤ n$. This is where I think the flaw is, because if $n$ is the single largest integer, then we'd get $n^2 &lt; n$ rather than $n^2 ≤ n$, so writing the latter is incorrect.
35440
I recently solved a , which says that,     A positive integer can be multiplied with another integer resulting in   a positive integer that is composed only of one and zero as digits.   How can I prove that this is true(currently I assume that it is). Also, is it possible to establish an upper bound on the length(number of digits) of the number generated?
51940
I have a question.  I have been given this proof: "For any $n$ in the integers where $n&gt;2$, show there are at least $2$ elements in $U(n)$ that satisfy $x^2=1$."  I have gone through and actually proved this, (that the numbers are $1$ and $n-1$) but i didn't' know how to prove that $n-1$ is in fact in the set $U(n)$. Is it because two consecutive numbers are always relatively prime?
122397
Donald Knuth &quot;The Art of Computer Programming&quot; Section 1.2.1 has an exercise No.2, the solution to which I don't understand. Exercise:  There must be something wrong with this proof. What is it? Theorem. Let $a$ be any positive number. For all positive integers $n$ we have $a^{n-1}=1$. Proof. If  $n = 1, a^{n-1}=a^{1-1}=a^0=1$. And by induction, assuming that the theorem is true for $1, 2, ..., n$, we have $a^{(n+1)-1}=a^n=\frac{a^{n-1}\times a^{n-1}}{a^{(n-1)-1}}=\frac{1\times1}{1}=1$; so the theorem is true for $n+1$ as well.  As far as I understand the proof by induction, the solution should be approximately following:$a^{1-1}=1$Assume that $a^{n-1}=1$;Therefore $a^{(n+1)-1}=1\times a$;So $a^{(n+1)-1}$ does not equal $a^{n-1}$ and does not equal $1$, unless $a=1$ The solution to exercise reads:  The theorem has not been proved for $n=2$; in the second part of the proof, take $n=1$; we assume there that $a^{-1}=1$. If this condition is true (so that $a=1$), the theorem is indeed valid.  I want to compare it to another, correct, proof by induction in the example from :  Adding up Odd Numbers $1+3+5+...+(2n−1)=n^2$  Show it is true for $n=1$ $1=1^2$ is True Assume it is true for $n=k$ $1+3+5+...+(2k−1) = k^2$ is True (An assumption!) Now, prove it is true for $(k+1)$ $1 + 3 + 5 + ... + (2k−1) + (2(k+1)−1) = (k+1)^2$We know that $1 + 3 + 5 + ... + (2k−1) = k^2$ (the assumption above),so we can do a replacement for all but the last term:$k^2 + (2(k+1)−1) = (k+1)^2$Now expand all terms:$k^2 + 2k + 2 − 1 = k^2 + 2k+1$And simplify:$k^2 + 2k + 1 = k^2 + 2k + 1$They are the same! So it is true.So: $1 + 3 + 5 + ... + (2(k+1)−1) = (k+1)^2$ is True   Returning to the first example, I didn't quite understand the meaning of the phrase  The theorem has not been proved for $n=2$;  In the second (correct) proof there is no proving that it holds for $n=2$, despite covering the same topic. And Knuth himself has the proof of the theorem $1+3+5+...+(2k−1) = k^2$ similar to the one above, where he too doesn't prove it for $k=2$. So what did he mean by this phrase? Does he mean that there already is an exception in the rule stated when we take arbitrary $n$, for example $n=2$, so therefore it wouldn't hold for all examples anyway? But taking arbitrary numbers and putting it into equation instead of $n$ doesn't seems to be an effective and systematic way to debunk such proofs. How would you explain what is wrong with the exercise?
79184
Excerpt from a mathematical proof that serves to prove by contradiction, using the Well Ordered Principle, that predicate P(n) is true for all nonzero integers n.     If n belongs to set C i.e. n >= c, then P(n) is false.      This implies the contrapositive,      If P(n) is true, n has to not be a part of set C i.e n &lt; c.   I know that the above implication is valid but why so? How should I know that n cannot take on 2 values simultaneously -- n being both >= c and &lt; c, thus P(n) being both true and false simultaneously? (Yes I am thinking Dialetheism, maybe even quantum logic but I know nothing other than that quantum logic defies certain aspects of propositional logic.) What is the basis behind a predicate (or any proposition) being either true or false? Or would the simultaneity be possible just that I wouldn't be dealing with a proposition to begin with?  Also, if you don't mind, please do let me know if you feel my understanding of concepts and terminologies (i.e. discrete, predicate, contrapositive, assume) are erroneous. I am extremely new to discrete mathematics and could really use the extra guidance.  Thank you.
34404
I tried to prove this question by first considering the possible last digit of $p$ when $p=n^2+5$, but that reasoning got me nowhere. Then I tried to prove it by contrapositive, and however I just couldn't really find where to start. Hence I'm here asking for some hints (only hints, no solution please).  Many thanks, D.
3244
Supposing that a real number $c$ is given, is the following true?  "If $n^c$ is a natural number for every natural number $n$, then $c$ is a non-negative integer."  Though this seems true, I can't prove that. Can anyone help?
89829
A number is removed from the set of integers from $1$ to $n$. Now, the average of remaining numbers turns out to be $40.75$. Which integer was removed?  By some brute force, I got $61$. I want to know if there's any analytic approach?
22623
I'd like to have my proof verified and if possible, to see other solutions that are interesting.  Proof: Suppose $n(n+1)$ is a square. Then we write $$n(n+1) = \prod_{p} p^{c(p)}$$ where $c(p) = a(p) + b(p)$ are such that \begin{align*} n &amp;= \prod_p p^{a(p)} \\ n+1 &amp;= \prod_p p^{b(p)} \end{align*} Now, by our hypothesis, $c(p)$ is even for all primes $p$. As $(n,n+1)=1$ for all $n$, it must be that $a(p)$ and $b(p)$ are even for all primes $p$ and moreover, $a(p) = 0$ whenever $b(p)&gt;0$ and reversely.  This indicates that both $n$ and $n+1$ are squares. This is impossible as there are no consecutive squares in the natural numbers.
4042
Problem: Is it true that $3$ never divides $n^2+1$ for every positive integer $n$? Explain.  Explanation: If $n$ is odd, then $n^2+1$ is even. Hence $3$ never divides $n^2+1$, when $n$ is odd.  If $n$ is even, then $n^2+1$ is odd. So $3$ could divide $n^2+1$.  And that is where I am stuck. I try to plug in numbers for $n$ but I want a more general form of showing that $3$ can't divide $n^2+1$ when $n$ is even.
64025
What is the greatest integer that divides $p^4-1$ for every prime number $p &gt; 5$?  This was on a practice math GRE so it's probably really easy.
55599
Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite.  At present I am factorizing the number $n$ to find the highest number $q$. I need a better approach which does not involve to factorize the number $n$ completely or by some other approach which is less than $O(\sqrt n)$. Constraint: $n\leq 10^{18}$  some test cases:   if $n=180$ then $q=6$  if $n=17$ then $q=1$ if $n=10000$ then $q=100$
67452
The following question popped up during a conversation with a friend of mine: is there any integer $n$ such that $n$ is not a square in $\mathbb{Z}$ but it is a square in every field $\mathbb{Z}_p$ with $p&gt;n$?  It sounds like an elementary question, and I am almost sure that the answer is no (mostly because of some distant memories of mine about a theorem of Hasse and Minkowsky), but I was not able to find a definitive answer.    I tried to apply some Model Theory to it, but I don't think it can be a fruitful path to follow. Another thing I noticed is that if I can prove that there is an $a$ such that $n=a^2$ in two different fields $\mathbb{Z}_p$ and $\mathbb{Z}_q$, then the the statement must be false: otherwise, writing $$a^2=n+bp$$ and $$a^2=n+cq$$ for the smallest possible $b$ and $c$, we would have $bp=cq$, a contradiction since neither $b$ nor $c$ can be $0$. But again, I got stuck after this consideration. Do you have any ideas or suggestions?
34769
These are all from Sipser's book, second edition. I was just hoping someone could verify/explain those that are more difficult for me.  $2n = O(n)$: true  $n^2 = O(n)$: false  $n^2 = O(n\log^2 n)$: I say false, because $\log^2 n$ grows more slowly than $n$  $n\log n = O(n^2$): true because $n$ grows more quickly than $\log^2n$  $3^n = 2^{O(n)}$: I wasn't sure what this notation meant. Any clarification here?  $2^{2^n} = O(2^{2^n})$: I would say true, but I'm not entirely sure why.  $n = o(2n)$: false, because $o(2n) = o(n)$ and $n$ grows as quickly as itself.  $2n = o(n^2)$: true, $n^2$ is always more than $2n$ for some constant.  $2^n = o(3^n)$: true  $1 = o(n)$: I'm not really sure.  $n = o(\log n)$: false, $n$ is always larger.  $1 = o(1/n)$: true, because 1 is always larger.
109777
This question came from  and from  where it's noted that "integers have a finite count of digits", so that the "number" in the title is not at all a number (not integer nor rational or real) . This statement seems to me justified because I suspect that if we admit an infinite count of digits we build a set of "numbers" that is not countable (but I've not a proof). I'm wrong?    Reading comments and answers I'm a bit confused. So I add a more specific question: Is the string in the title a number in some model of Peano Axioms?
122461
Let $p(n)$ denote the largest prime factor of $n$. Prove that there are infinitely many $n$ such that $$p(n)&lt;p(n+1)&lt;p(n+2).$$  Edit:   My solution: Choose $n=\prod_{i=1}^{k}p_i$, product of the first $k$ primes. This means that $n+1=\prod_{i=1}^{k}p_i+1$ is either a larger prime or has a prime factor larger than that of all factors of $n$. Still not sure about $n+2$.
115559
I have been trying to show these two inequalities hold for all positive integers n, but I don't know how to proceed at all... I have tried playing around with them but I didn't find anything helpful. I have also tried induction but I couldn't make it work.