1
vote
1answer
59 views

Proof by contradiction: logarithm

I need to prove by contradiction that $\log_2(3)$ is irrational. I'm really unfamiliar with logs to be honest, it's been awhile since I've done them and I'm unsure of how to approach this. Any help ...
5
votes
5answers
766 views

Proof of infinitely many primes, clarification

Proof: The proof is by contradiction. Suppose there are only finitely many primes. Let the complete list be $p_1,p_2,\dots,p_n$. Let $N = p_1p_2 \dots p_n+1$. According to the Fundamental Theorem of ...
2
votes
5answers
63 views

Proof regarding divisibility

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$ I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do ...
1
vote
3answers
47 views

Proof for modulus via direct or contrapositive

I have to prove the following via direct proof or via contra positive. For $a,b\in \mathbb{Z} $ it follows that $ (a+b)^3 \equiv a^3 + b^3 \mod 3$ I'm unsure of the best way to approach this ...
1
vote
0answers
40 views

What is the relationship between division and proving an integer is odd?

I am trying to use proof by contradiction to prove: $101$ is an odd integer. I know that the first step is to assume that $101$ is even, so: $101 = 2q, q \in \mathbb{Z}$ Then I am stuck. I don't ...
0
votes
0answers
41 views

Proof by Induction for Fundamental Thm of Arithmetic

Use induction to make our proof of the Fundamental Theorem of Arithmetic more rigorous. Recall that $p$ is prime iff for all $a,b\in\mathbb Z:p\mid(ab)$ implies $p\mid a$ or $p\mid b$. Prove that ...
1
vote
3answers
62 views

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ [duplicate]

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ How would you do the inductive step for this proof? I have the base case done.
1
vote
2answers
50 views

Proving $2^x$ is only ever 9 less than a perfect square for a unique value of x

I am trying to prove something that has essentially boiled down to proving that $9 + 2^x$ will only ever be a perfect square for the unique value of x=4, and that no other value will produce a perfect ...
5
votes
5answers
454 views

Positive integers expressable as sums of powers of 2

I need to prove that any positive integer is expressable as $$x=2^{j_0}+2^{j_1}+2^{j_2}+...+2^{j_m}$$ where $m\ge 0$ and $0\le j_0\lt j_1\lt j_2\lt ... \lt j_m. $ I think I get the gist of the proof; ...
2
votes
6answers
96 views

Investigating the linearity between squares and their roots

I recently noticed that $\sqrt{128} = 11.31$ and that $128$ is $\approx 30\%$ between $121 = 11^2$ and $144=12^2$, that is: $$ \frac{128-121}{144-121} = \frac{7}{23} \approx 30\%$$ and $\sqrt{128} = ...
1
vote
2answers
60 views

Ground Plan - Prove Fermat-Euclid's Totient Theorem with Lagrange's Theorem

If $\gcd(a,n) = 1$, then $a^{\phi(n)}\equiv 1\pmod n$. Here's a three-step proof. An integer a is invertible means there's some $a^{-1}$ such that $aa^{-1}\equiv 1 \pmod n$. By cause of Jones p84 ...
4
votes
2answers
166 views

Fermat's Little Theorem fails for composite instead of prime numbers.

I know Fermat's Little Theorem = Fermat-Euler's Totient Theorem when $n$ is prime. Elementary Number Theory, Jones, p83 writes if we simply replace p with a composite integer n, then the ...
2
votes
1answer
59 views

Backward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p) $.

(1) How can you preconceive to prove by contradiction? Prove by contradiction. Suppose $n$ is composite. This means there exists a divisor $d|n$ such that $1<d<n$. We are given that ...
1
vote
2answers
38 views

Ground Plan – Forward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p) $.

Lemma 5.3 - I omit proof here - Let p be prime. Then $x^2 \equiv 1 \, (mod p) \iff x \equiv \pm 1 \; (mod p)$ First we establish the result for the first two primes 2, 3. Then prove the result for ...
3
votes
1answer
89 views

Ground plan of Forward direction - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$

Prove by contradiction. Thence suppose NOT $p\equiv 1 \; (mod 4)$. Thence 3 possibilities remain: $4|p, 4|(p - 2), 4|(p - 3)$. But $p > 2$ is prime, thence $4 \not | p$. (1) How can you ...
3
votes
1answer
169 views

Ground plan of Backward direction (<=) - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$

Apply the identity $p-i \equiv -i \mod p$ for $i=1, \ldots$ to the pink factors $ \begin{align} \color{seagreen}{ (p-1)! } = 1\times 2\times\cdots\times \dfrac{p-1}{2} & \times \quad ...
2
votes
2answers
71 views

Proving that repeating decimals can be rewritten as fractions without using infinite series

I'm being asked to prove that all repeating decimals can be written as fractions. The catch is that I'm not allowed to use infinite series, so that excludes most if not all methods I've seen so far. ...
1
vote
1answer
45 views

Chinese Remainder Theorem - Ground Plan of Existence Proof

Let $n_{1},\ n_{2},\ n_{3},\ \cdots,\ n_{r}$ be positive integers such that $\gcd(n_{i}, n_{j})=1$ for $1 \le \quad i\neq j \quad \le r$ Then the simultaneous linear congruences $ x\equiv a_i \pmod ...
2
votes
3answers
38 views

Prove that if m is prime and m|kl then either m|k or m|l.

Proofs homework question, here's what I've figured out thus far. Suppose m doesn't divide k. We need to then prove that m|l. If m doesn't divide k and m is a prime then we know m and k are co-prime ...
0
votes
4answers
53 views

How to prove that if a number is divisible by two other numbers, then it is divisible by there product

I would like to prove if $a \mid n$ and $b \mid n$ then $a \cdot b \mid n$ for $\forall n \ge a \cdot b$ where $a, b, n \in \mathbb{Z}$ I'm stuck. $n = a \cdot k_1$ $n = b \cdot k_2$ $\therefore a ...
0
votes
3answers
23 views

Let $a$ be a positive integer. The sum of $a$ consecutive integers is divisible by $a$ if and only if $a$ is odd.

How would one prove this? Other than using cases to prove the if and only if part, how would I prove each case to complete the proof?
0
votes
3answers
108 views

How to prove if $n$ is prime and $n | a^2$ then $n | a$?

My professor assigned this for homework but I don't understand how to connect the dots. He suggested using the fact that $\gcd (x,y) \cdot \operatorname{lcm} (x,y) = xy$ but I'm not sure how that's ...
2
votes
1answer
82 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
2
votes
1answer
71 views

Proof - Fundamental Theorem of Arithmetic using Euclid's Lemma

Let $n \in Z > 1$. Then the expression for $n$ as the product of $\ge 1$ primes is unique, up to the order in which they appear. From Proofwiki. Suppose $n$ has two prime factorizations: ...
2
votes
1answer
49 views

Linear Congruence Theorem - Are these solutions too? Where'd they hail from?

(1) Can't the signs - I colored them in red - of x and y be switched? Aren't $x = x_0 - bn/d$ and $y = y_0 + an/d$ also solutions? They satisfy $ax + by = c$? (2) How can I remember these ...
0
votes
3answers
37 views

Divisibility proof by induction.

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
0
votes
1answer
52 views

How to show that if $ p \equiv 1,3 \pmod 8$ then there exists a $u,v \in \mathbb Z: u^2 + 2v^2 = p$

I'm trying to show this statement: $$p \equiv 1,3 \pmod 8, \; \; \exists \; u,v \in \mathbb Z : u^2 + 2 v^2 = p.$$ I believed I proved it the other direction using the ring $\mathbb Z{\sqrt{-2}}$. ...
0
votes
1answer
62 views

Proving $\left\lfloor n\frac{\log (b)}{\log (a)}\right\rfloor =\left\lfloor \frac{\log \left(b^n+1\right)}{\log (a)}\right\rfloor$

Inspired by this question, I'd like to know how one would go about proving the below more general equation? $$n \in \mathbb{N},\;a \in \mathbb{N},\;b \in \mathbb{N}$$ $$b^n+1 \notin ...
1
vote
2answers
62 views

Prove that a pair of irrational numbers is the solution to a quadratic polynomial.

Suppose a, b are two irrational numbers such that ab is rational and a+b is rational. Then a, b are the solution to a quadratic polynomial with integer coeffecients.
2
votes
2answers
36 views

Prove that for all integers $n\geq 2, n^3+1>n^2+n$

I am attempting this by induction. Base case $2^3+1 >2^2+2 \implies 8>6,$ which is true. Now the induction step $(n+1)^3+1>(n+1)^2+(n+1),$ which simplifies to $n^3+3n^2+3n+2 > n^2+3n+2.$ ...
0
votes
2answers
75 views

Proving that if $a^2+b^2=c^2$ for $a,b,c \in \Bbb Z^+$, then either $a$ or $b$ is even. [closed]

Prove that if $a, b, c \in \Bbb Z^+$, and $a^2+b^2=c^2$, then either $a$ or $b$ is even. It seems like a proof by contradiction can be used here. I have my own proof below but it may need some ...
0
votes
0answers
43 views

Is it a surjection?

Consider the sequence given by $u_1=2$ and $u_{n+1}=\{\min k: \gcd (k,u_n)>1$ and $k$ has not appread in the sequence before} Show that the this sequence is surjective on $N\setminus \{1\}$ I ...
1
vote
4answers
26 views

If $a$ and $b$ are odd, prove $\gcd(a,b) = \gcd(\frac {\left| {a-b} \right |} {2}, b)$

Honestly I don't have a strong idea. I don't know where to even begin, I have considered that the $\gcd(a,b)$ is somehow less than $a-b$, but I'm not even sure why that would be the case.. Any help ...
1
vote
3answers
158 views

If $\gcd(a, b) = 1$ and if $ab = x^2$, prove that $a, b$ must also be perfect squares; where $a,b,x$ are in the set of natural numbers

Problem: If $\gcd(a, b) = 1$ and If $ab = x^2$ ,prove that $a$, $b$ must also be perfect squares; where $a$,$b$,$x$ are in the set of natural numbers I've come to the conclusion that $a \ne b$ and ...
3
votes
2answers
122 views

Intuition — If $k \in \mathbb{Z}$ and $n \ge 2$, then the n$^{th}$ root of k is either an integer or irrational.

Origin — Elementary Number Theory — Jones — p25 — Exercise 2.4 (1) How do you prefigure the answer? Proofwiki start after prefiguring it. (2) What's the intuition? This answer ...
0
votes
0answers
43 views

I need help prooving a theorem in OEIS A224914

I've tried to solve this, but can't seem to get anywhere. Full description is in the pdf. http://blogoff.simonjensen.com/#post18 http://www.simonjensen.com/pdf/The_answer_is_47.pdf ...
2
votes
2answers
114 views

Product of $n$ consecutive positive integer is not a $n$th power?

If $n>2$ and $k$ is positive integer, then there is no positive integer $m$ satisfy that $$k(k+1)\cdots (k+n-1)=m^n\, ?$$ I tried to prove this problem, but I don't know how to prove it. I know ...
-1
votes
2answers
60 views

Discrete Mathematics Proof Question

Prove or disprove that there are infinitely many $x, y, z \in \mathbb N$ such that $$\frac{1}{x^2} + \frac{1}{y^2} = \frac{1}{z^2}$$ Currently, I tried to substitute $x, y,$ and $z$ with $2n$ and $n$ ...
0
votes
1answer
84 views

Prove or disprove the following statement. $7 \ | \ (x^3 + x^2 + x + 2)$, where $x$ is an odd integer

We're learning about modulus and division (Discrete mathematics and proofs course). I'm not exactly sure how to tackle this sort of problem, is there some sort of property of cubic functions ...
2
votes
2answers
94 views

Help with the algebra in for this number theory proof?

For all $n\geq 1$, prove with mathematical induction $\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ So far.. I have substituted 1 and saw that the statement is ...
0
votes
2answers
99 views

Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
2
votes
1answer
109 views

Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.

I am confused as to how to solve this question. For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a ...
-1
votes
2answers
72 views

Show that $z$ is prime if $z|xy$ implies $z|x$ or $z|y$

Let $z$ be an integer greater than or equal to $2$. Suppose for all integers $x$ and $y$ that $z|xy$ implies $z|x$ or $z|y$. Show that $z$ is prime.
7
votes
4answers
264 views

For which primes p is $p^2 + 2$ also prime?

Origin — Elementary Number Theory — Jones — p35 — Exercise 2.17 — Only for $p = 3$. If $p \neq 3$ then $p = 3q ± 1$ for some integer $q$, so $p^2 + 2 = 9q^2 ± 6q + 3$ is divisible by $3$, ...
3
votes
5answers
186 views

Intuition — An integer $n > 1$ is composite $\iff \color{purple}{p \le \sqrt{n}}$ divides it.

Origin — Elementary Number Theory — Jones — p32 — Lemma 2.14 Backward direction — I need to prove there exists a divisor $d$ of $n$ satisfying $1<d<n$. Because $p$ is prime, $1 < p$. ...
5
votes
2answers
120 views

Proof - There're infinitely many primes of the form 3k + 2 — origin of $3q_1..q_n + 2$

Origin — Elementary Number Theory — Jones — p28 — Exercise 2.6 To instigate a contradiction, postulate $q_1,q_2,\dots,q_n$ as all the primes $\neq 2 (=$ the only even prime) of the form $3k+2$. ...
4
votes
1answer
549 views

Proof — Infinitely many primes of the form $4k + 3$ — origin of $4(p_1…p_k - 1) + 3$

I know there are sundry questions — like this pdf — and this (10.) Prove that any positive integer of the form $4k + 3$ must have a prime factor of the same form. Because $4k + 3 = 2(2k + 1) + 1$, ...
5
votes
3answers
77 views

Do Question's Given GCD Statements Imply these New GCD Statements?

Are the following statements true or false, where $a$ and $b$ are positive integers and $p$ is prime? In each case, give a proof or a counterexample: (b) If $\gcd(a,p^2)=p$ and ...
0
votes
3answers
61 views

Deductions from Carmichael's theorem

1.) May I seek your advice on how to prove the following assertion(without recourse to (2)): If $ 2014 \equiv 14 \ (\text{mod} \ 2000), $ then $2014^{2014} \equiv 14^{14} \ (\text{mod 2000}).$ 2.) ...
3
votes
1answer
68 views

Elementary number theory problem

Let $X = \{n \in \mathbb{N}: 6 \times n\,\, \text{does not consist of} \ 0,1,2,3 \, \text{or} \ 4\}.$ For eg, $93 \in X$ because $6 \times 93=558.$ Could anyone advise me how to prove there ...