3
votes
1answer
26 views

Generalized Pythagorean triples construction.

All primitive Pythagorean triples $(a, b, c) : \{ a^2 + b^2 = c^2 \} \wedge \{ a \equiv 0 \pmod{2} \}$ can be expressed in the form:$$\{ a = 2pq, b = p^2 - q^2, c = p^2 + q^2 \}$$ for positive ...
-5
votes
0answers
56 views

A starting point for the Erdos-Straus Conjecture [closed]

According to the Erdos-Straus conjecture, could we consider the following as a new approach? $$\frac{4}{n}=\frac{1}{n^2}+\frac{1}{n^2}+\frac{1}{n^2}+\frac{\lambda}{n^2},$$ where $\lambda=n+3(n-1).$ ...
0
votes
2answers
34 views

Proof for: GCD and divisibility

I need some hints how to proof something like the following: Let $a,b \in \mathbb{Z}$ with $a,b \not= 0$ and let $\gcd(a,b)=d$. (1) For any $m,n\in \mathbb{Z}$ we have $d \mid ma+nb$. (2) There ...
0
votes
0answers
37 views

Proof of two properties of a simple math function

I would like to define a function to evaluate the value for some entities which receive a number of "up"s ($\mathcal{u}$) and "down"s ($\mathcal{d}$). I devised the following function: ...
0
votes
1answer
35 views

The set of all real numbers $\epsilon$ with $0 < \epsilon < 1$ is equinumerous with the set of all sets of positive integers

How is a proof like this normally conducted? I know that Cantor's theorem may prove useful here, but I'm having trouble extending the definition to problems that are (seemingly) unrelated.
0
votes
1answer
28 views

Show that the set of all subsets of an infinite enumerable set is not enumerable

I know this problem involves using Cantor's theorem, but I'm not sure how to show that there are more subsets of an infinite enumerable set than there are positive integers. It seems like a lot of ...
0
votes
2answers
72 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
0
votes
1answer
54 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...
0
votes
2answers
72 views

Show that, given regular expression $R$, we can decide whether $L(R)$ is prefix-free

Suppose language $L$ is called prefix-free if no member is a proper prefix of another. For instance, cat is a proper prefix of category and so $L = \{cat,category,ego,go,rye\}$ is not prefix free. ...
0
votes
1answer
177 views

Show that two disjoint languages are not separable

What is the general method to show that two disjoint languages are not separable? As an example, suppose we have: $A = \{\langle M \rangle : M ( \langle M \rangle )$ halts and says ACCEPT$\}$ $B = ...
1
vote
1answer
22 views

Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
1
vote
1answer
50 views

Showing $\sum_{n\in\mathbb{N}}\frac{\Lambda(n)}{n}=\log (x)+O(1)$ using a given result.

I'm stuck on the following problem. Use the fact that $$\sum_{p\le x}_{p\,\text{prime}}\frac{\log p}{p}=\log (x)+O(1)$$ to show that $$\sum_{n\le x}_{n\in\mathbb{N}}\frac{\Lambda(n)}{n}=\log ...
0
votes
0answers
40 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 ...
0
votes
2answers
67 views

Gaussian integers - If $N(t)$ is an ordinary prime, prove then $t$ is a Gaussian prime

$\mathbb{Z}[i] = \{a+bi | a,b\in\mathbb{Z}\}$ Show that if $N(t)$ is an ordinary prime in $\mathbb{Z}$ then $t$ is a Gaussian prime in $\mathbb{Z}[i]$ (we say that $t\in\mathbb{Z}[i]$ is a Gaussian ...
2
votes
2answers
92 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
82 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 ...
1
vote
2answers
73 views

Can consecutive integers be perfect powers?

I have been wondering whether consecutive integers can ever be perfect powers.And even if they can, how many consecutive integers at most can be perfect powers?My intuition tells me that consecutive ...
0
votes
2answers
42 views

Significance of low order terms in base expansion of integer square root

My head is turning into a uniform gel of random thoughts! I cannot see a proof or find a counterexample to the following: Conjecture: Let integer $x$ be expressed as $a_3 \, b^3 + a_2 \, b^2 + a_1 \, ...
1
vote
2answers
78 views

Multiplicative inverses for $Z_n$

Whilst reading I came across the strange claim that multiplicative inverses exist for only prime values of $n$ in $Z_n$. I am a little puzzled as contrary to that, I know that additive inverses exist ...
1
vote
2answers
110 views

Primitive Roots Proofs

I am stuck on how to prove these two questions: (1) Let r be a primitive root of the prime $p$ with $p$ congruent to $1$ modulo $4$. Show that $-r$ is also a primitive root. (2) Let n be a positive ...
6
votes
0answers
93 views

Prove that $3x^3+4y^3+5z^3 \equiv 0 \pmod{p}$ is solvable for all primes p

I am trying to prove that the congruence $3x^3+4y^3+5z^3 \equiv 0 \pmod{p}$ is solvable for all primes p. I proved it using primitive root, but my professor in number theory told me that it can be ...
2
votes
1answer
66 views

Pythagorean triangle question

Let $n$ be a positive intger. Prove that if there is at least one primitive Pythagorean triangle where one side is n units less than the hypotenuse, then there are infinitely many. I thought of ...
0
votes
1answer
100 views

simple proof of a theorem that is weaker than chen's theorem?

I want to see a simple proof of a theorem that is weaker than chen's theorem. Thus let $m,n$ be positive integers. An m-almost prime is a squarefree integer that is the product of at most $m$ primes. ...
4
votes
4answers
284 views

A short or elegant proof for if $p | n^2$ then $p | n$ when $p$ is prime?

Let $n, p \in \mathbb{Z}^{+}$ such that $p$ is prime. Prove $p | n^2 \Rightarrow p | n$. What is a short or elegant proof to this? Some ideas are given at the question Prove that $\sqrt 5$ is ...
0
votes
2answers
94 views

Using induction to prove that every integer can be written in a particular form

(a) Use induction to prove that every integer $n$ can be written in the form: $$n = \beta_0 3^0 + \beta_1 3^1 + \cdots + \beta_{r-1} 3^{r-1} + \beta_r 3^r$$ where $r$ is a non-negative ...
2
votes
2answers
80 views

Showing that a system of Diophantine equations will have irrational solutions as well as integers

Solve $\begin{cases} 3xy-2y^2=-2\\ 9x^2+4y^2=10 \end{cases}$ Rearranging the 2nd equation to $x^2=\dfrac{10-4y^2}{9} \Longrightarrow 0\leq x^2 \leq 1$ if $x^2=1$ than $y=\pm\dfrac{1}{2}$ and ...
2
votes
2answers
79 views

Proof that if $x, y \in \mathbb{Z}$ then $xy \in \mathbb{Z}$

How do you prove that the product of two integers is an integer?
2
votes
1answer
24 views

Prove that for all $a\in \mathbb Z$, $a>2 \Rightarrow a \nmid b$ or $a \nmid (b +1)$

Prove that for all $a\in \mathbb Z$, $a>2 \Rightarrow a \nmid b$ or $a \nmid (b +1)$ I understand direct proof techniques and contrapositive proofs but I'm stumped on how to go about this.
1
vote
1answer
248 views

Show that the gcd of an odd integer and an even integer is odd

I am using the definition of odd and even integers along with bezout's theorem and I end up with something of the form $d=(2k)m+(2l+1)p$ where $a=2k$ and $b=2l+1$. I've tried to use contradiction as ...
0
votes
1answer
47 views

Question about $\mathbb{Z}_n$ and $G_n$

For $n ≥ 2$ we let $G_n ⊂ Z_n$ denote the subset of all integers mod n which are invertible $\mod n$. Let $m, n \in \mathbb{Z}$ $m, n ≥ 2$ and $(m, n) = 1$. Define a mapping $f : Z_m × Z_n → Z_{mn}$ ...
3
votes
0answers
43 views

How does Hildebrands proof of the prime number theorem via large sieve work?

How does the sieve inequality (I may not know the most general form) lead to the distribution of primes? To me, these concepts do not seem to be related. Can their connection be described in a ...
6
votes
1answer
211 views

Prove that $\sum_{\substack{0<k<3^n\\3\nmid k}}\sigma{(3^n-k)}\sigma{(k)}=6\cdot27^{n-1}$

A similar problem to this problem (ccorn has given a nice answer to it). Prove that $$\sum_{\substack{0<k<3^n\\3\nmid k}}\sigma{(3^n-k)}\sigma{(k)}=6\cdot27^{n-1},$$ where $\sigma(N)$ is ...
0
votes
4answers
1k views

Proof of the statement “The product of 4 consecutive integers can be expressed in the form 8k for some integer k”

I am slowly diving into simple number theory and learning how to craft direct proofs. I needed to proof the statement "The product of 4 consecutive integers can be expressed in the form 8k for some ...
11
votes
5answers
2k views

Why does one counterexample disprove a conjecture?

Can't a conjecture be correct about most solutions except maybe a family of solutions? For example, a few centuries ago it was widely believed that $2^{2^n}+1$ is a prime number for any $n$ . For ...
2
votes
2answers
55 views

Is this recursion relation proof correct?

Recurrence relation:$$a_0 = 1$$ $$a_{n+1} = 2a_n$$ I'm trying to prove that for any n ∈ N, $a_n = 2^n$. I want to use induction. What I have is, assume that $a_n = 2^n$ is true for $P(n)$. Then ...
5
votes
2answers
178 views

Proof of the infinitude of primes by probabilistic methods.

I'm looking if there is proof of the infinitude of prime numbers using probabilistic method. I am motivated by the answer of my question here. The answer is based on a relationship between ...
1
vote
1answer
245 views

Proof by contrapositive with division

Proof by Contraposition. Include the contrapositive statement. If the product of two integers is not divisible by some integer $n$; then neither integer is divisible by $n$. I know you negate ...
8
votes
1answer
270 views

A simple way to obtain $\prod_{p\in\mathbb{P}}\frac{1}{1-p^{-s}}=\sum_{n=1}^{\infty}\frac{1}{n^s}$

Let $ p_1 <p_2 <\ldots <p_k <\ldots $ the increasing list in set $\mathbb{P}$ of all prime numbers . It is well known (by Infinite geometric series $\sum_{k=0}^\infty r^k = \frac{1}{1-r}$ ...
8
votes
1answer
234 views

Proving that $\omega(N)\neq4$ for an odd perfect number $N$ by hand

Let $\omega(n)$ denote the number of distinct prime factors of a positive integer $n$, and let $N$ be an odd perfect number. It is not difficult to show that $\omega(N)\ge3$. In fact, Nocco already ...
4
votes
2answers
3k views

This is a possible proof of the Riemann Hypothesis [closed]

http://arxiv.org/abs/1305.6845 The above link claims to have solved the Riemann Hypothesis. It's not mine, of course. I just saw this on Tumblr and realized I needed bigger guns. This proof looks like ...
3
votes
1answer
81 views

$\mathbb{Z}/m\mathbb{Z}$: A Complete Set of Representatives

So, I'm letting ${\scr{A}}=\{a_1,\dots,a_n\}$ be a complete set of representatives (C.S.R.) for $\mathbb{Z}/m\mathbb{Z}$. I'm considering all $b\in \mathbb{Z}$ and seeing if ${\scr{B}}=\{a_1+b, a_2+b, ...
3
votes
2answers
47 views

Show that $\exists A \subset \mathbb{R}$ such that $\forall x$ $\in \mathbb{R}$, we may write $x$ uniquely as $x=a+q$, where $a\in A,q\in\mathbb{Q}$.

Not sure where to go with this one. Clearly will have to use the axiom of choice at some point. I haven't been able to think of a good example for the set A. Once we've got that, it'd be a matter of ...
1
vote
2answers
125 views

Sum of divisors is prime implies number of divisors is prime.

I've seen this posted but I haven't seen this in depth as i need it. I turned this in as homework but only got 1 out of 3 on it, so any clarification would be wonderful. Show that if the sum of all ...
0
votes
2answers
83 views

Showing unique solutions to simultaneous linear congruences exist

Show that if $p$ is prime, then the simultaneous linear congruence $$ax + by \equiv u \pmod{p}$$ $$cx + dy \equiv v \pmod{p}$$ has a unique solution $x, y$ modulo $p$ when $ad-bc \not\equiv 0 ...
15
votes
2answers
319 views

How can I prove my conjecture for the coefficients in $t(x)=\log(1+\exp(x)) $?

I'm considering the transfer-function $$ t(x) = \log(1 + \exp(x)) $$ and find the beginning of the power series (simply using Pari/GP) as $$ t(x) = \log(2) + 1/2 x + 1/8 x^2 – 1/192 x^4 + 1/2880 x^6 - ...
1
vote
2answers
76 views

Interesting digits proof

I recently started writing the programming practice questions in TopCoder, and one question is about Interesting Digits: An digit $D$ in base $B$ is interesting if for all multiple $X$ of $D$ (in ...
0
votes
4answers
47 views

Prove that if $a$ is a prime, $b_i \in \mathbb{Z}_+$ and $a | \prod_{i = 1}^{n} b_i$ then $a | b_i$ for some $b_i$

A key property of the integers is that: if $\gcd(a,b) = 1$ and $a |bc$, then $a|c$. Use this property to prove that: if $a \in\mathbb{Z}_+$ is prime and $b_i \in \mathbb{Z}_+$ for $1 \leq i \leq n$ ...
1
vote
1answer
50 views

Given $p(x)$ is a polynomial of degree $n$, and $r$ to be its root, how to prove that $|r| \le \max(1, \sum_{i=1}^n |{a_i \over a_0}|)$?

Let $p(x)=a_0x^n+a_1x^{n-1}+\cdots+a_n,a_0 \ne 0$ to be univariate (1 variable) polynomial of degree $n$. Let $r$ be its root, i.e. $p(r)=0$. How can I prove that: $$|r| \le \max\left(1, ...
3
votes
1answer
138 views

How to prove that $0.01001100011100001111…$ is not periodic decimal number?

I have the following decimal number: $0.01001100011100001111...$ Notice how whenever we have one 0, we also have one 1, two 0's, two 1's, etc. How do you continue it to infinity and prove that this ...
6
votes
2answers
324 views

Resource for Vieta root jumping

I can't seem to find a good resource on Vieta's root jumping, which would explain various scenarios that suggest using the technique. Does anyone have a suggestion for a reference?