0
votes
1answer
19 views

Proving that any common multiplication of two numbers is a multiplication of their least common multiplication

Im trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multipe is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple ...
0
votes
2answers
64 views

how to find taxicab numbers but for squares?

Natural numbers that can be written as the sum of squares in two or more ways. The first ten numbers are 50, 65, 85, 125, 130, 145, 170, 185, 200, 205. $$ n = a^2 + b^2 = c^2 + d^2\\ a^2 − c^2 = d^2 ...
2
votes
0answers
83 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
0
votes
0answers
55 views

Prove the inequality $\sum_{i,j = 1}^n {{A_{i,j}}({x_i}^2 - {x_i}{x_j})} \ge 0 $

A is a square matrix with positive elements and x is a real vector (both of them n>1 dimensional). Prove that for any such matrix and vector $$\sum\limits_{i,j = 1}^n {{A_{i,j}}({x_i}^2 - {x_i}{x_j})} ...
-1
votes
2answers
282 views

What is the efficient way to calculate number of divisors of N that are divisible by 2?. [closed]

For example if a number is given let say 8 then its factors are 1,2,4,8 hence total numbers of divisors which are divisible by 2 are (2,4,8) that is 3.
2
votes
1answer
31 views

The number of distinct multiples of composites greater than $n$ that can be factored into two naturals less than or equal to $n$

Given a list of composites between $n$ and $\lfloor \frac{n^2}{2} \rfloor$: What would be the most efficient way to count, for each composite, the number of its distinct multiples that can be ...
0
votes
0answers
21 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
1
vote
0answers
18 views

How do I prove this equality involving ceilings and max?

For all $T \in \mathbb{N}$ the following holds, with $k \in \mathbb{Z}$ and $m, n \in \mathbb{N}$: $$\left \lceil \frac{k \cdot m}{n} \right \rceil + T - 1 = \max_{0 \leq i < T} \left \{ i + T ...
1
vote
1answer
63 views

The relationship between each harmonic numbers

In Knuth's "Concrete Mathematics" in chapter about numbers below equality is given $$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{\epsilon_n}{120n^4} $$ where $0 < \epsilon_n < ...
0
votes
1answer
38 views

How to test mathematically if a number contains the highest digit of its radix?

Is there a way to test mathematically if a number contains the highest digit of its radix, and if so how? For example, 101 in base 2 contains the digit 1, highest in base 2; but 101 in base 3 does ...
3
votes
1answer
67 views

Determine Units of a Ring $\mathbb{Z}[\alpha]$

I am trying to determine the units of $Z[\alpha]$ where $\alpha$ satisfies the monic polynomial $\alpha^4+\alpha^3+\alpha^2+\alpha+1$. I found $Z[\alpha] := \lbrace a+b\alpha+c\alpha^2+d\alpha^3\;|\; ...
0
votes
1answer
31 views

Modulation and translation properties of DFT

Consider the discrete fourier transform over a finite field $GF(q)$. Let also $\omega$$\in$$GF(q)$ be an element of order $n$ and which is an $n$-th root of unity. Definition 1. Let $v$ = ($v_0$, ...
2
votes
1answer
44 views

Prove $\gcd(k, l) = d \Rightarrow \gcd(2^k - 1, 2^l - 1) = 2^d - 1$ [duplicate]

This is a problem for a graduate level discrete math class that I'm hoping to take next year (as a senior undergrad). The problem is as stated in the title: Given that $\gcd(k, l) = d$, prove that ...
0
votes
2answers
51 views

integer solution to an equation - do solutions exist?

prove or find a counterexample: The equation $x^n + y^n = z^n$, where $n$ is a natural number, has no solutions at all where $x, y,z$ are integer. counterexample: if $n=3$ and $x=1$ and $y=2$ and ...
3
votes
2answers
93 views

why generating function $A(z) = 1 + z + z^2 + \cdots$ can be denoted as $\frac{1}{1-z}$

It is easy to see that $1 + z + z^2 + \cdots$ is equal to $\frac{1}{1-z}$ when $1 > z > 0$ and for $z >= 1$, they are not equivalent. So I have thought $\frac{1}{1-z}$ is just a short for the ...
0
votes
2answers
34 views

Proving something is primitive recursive

I'm trying to prove $f(n) = 2n$ is primitive recursive. I understand that for something to be primitive recursive it must have the following properties: $0(x)=x$ the zero function $s(x)= x+1$ the ...
-1
votes
1answer
28 views

need help With Numbering system [closed]

Given $1000 in $1 dollar bills and 10 envelops, distribute the money among the envelops so that you can give out any dollar ...
0
votes
1answer
39 views

1:1 and onto proof of Z+ and Q+

I'm looking for help finishing this proof The details are laid out here: http://www.physicsforums.com/showthread.php?p=4733092#post4733092 if that doesn't work here is another format ...
0
votes
2answers
95 views

Prove $x$ and $y$ in $y = x^2 + 2$ are prime only for $x = 3$ and $y = 11$?

Let $x$ be a positive integer and $y = x^2 + 2$. Can $x$ and $y$ be both prime? The answer is yes, since for $x = 3$ we get $y = 11$, and both numbers are prime. Prove that this is the only value of x ...
0
votes
2answers
185 views

Discrete math: probability of picking certain hands with a preset condition

In 5-card draw poker, a player receives an initial hand of 5 cards, and is then allowed to replace up to three of her cards with the remaining cards in the deck. (b) Suppose that, among the initial 5 ...
2
votes
1answer
152 views

Is my conjecture correct? Any advice on how to solve this conjecture?

I was doing problem 6.3 from here. To make this less programming and more math oriented: GCDMany is equivalent to using Euclid's method (using mods and NOT ...
1
vote
4answers
63 views

Show that if $p$ is a prime number $> 3$ then $24 \mid p^2-1$ [duplicate]

Hi guys can someone help me with this ?(Without using Modular arithmetic) Show that if $p$ is a prime number $>3$ then $24$ $\mid$ $p^2-1$
1
vote
1answer
39 views

Find all solutions to the Diophantine equation $2x+3y =1$.

How to find all the solutions to the Diophantine equation $2x+3y =1$. My professor didn't explain to us how to do this.
0
votes
2answers
73 views

Proof that 2 and 3 are the only siamese twins that exist!

Let us say that two prime number p and q are siamese twins if |p-q|=1. List all the siamese twins that exist, and prove your list is complete. Proof: 2 and 3 are prime numbers and 3-2=1. Therefore 2 ...
0
votes
2answers
30 views

to show one to one function

how we can show f(x)=-x^2+6x-7 , if x is less than or equal 3 one to one?? DO we use a quadratic formula?? f(x)=-x^2+6x-7= 2-(x-3)^2. f(x)=f(y) implies x=y which is injective or one to one. ...
0
votes
1answer
18 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
1
vote
2answers
31 views

Number theory and divisibility proof

If a|b and a|b+2, how do I prove that a must be either a=2, or a=1? I know that $b=aq$ and $b+2=ap$. $aq+2=ap$ And now I don't know what to do with it.
1
vote
1answer
21 views

Definition of a lattice point being primitve

I was reading an article and came across the following definition: a lattice point is called $\it{primitive}$ if it is part of a basis of the lattice. Suppose I have a lattice $\Lambda$ in ...
1
vote
4answers
145 views

What's the easiest way to factor $5^{10} - 1$?

What's the easiest way to factor $5^{10} - 1$? I believe $5 - 1$ is a factor based off the binomial theorem. From there I do not know. We are using congruence's in this class.
2
votes
1answer
65 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
14
votes
2answers
246 views

Minimum number of operations (divide by 2/3 or subtract 1) to reduce $n$ to $1$

This question is inspired by a Stack Overflow question which involves the task to find an algorithm to solve the following problem: Given a natural number $n$, what is the least number of moves ...
0
votes
1answer
71 views

An easy question with integer numbers

I have an easy question of arithmetic. Let $a, b, N$ be integer numbers such that $\mathrm{gcd}(a,b,N) = 1$. Is it true that there exists an integer number $x \in \mathbb{Z}$ such that ...
0
votes
1answer
60 views

More transcendental numbers than natural numbers [duplicate]

Are there any simple proofs that obtain this result? I haven't been able to find one online.
1
vote
1answer
35 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
2
votes
3answers
100 views

Show that the set of all infinite subsets of $\mathbb{N}$ has cardinality greater than $\mathbb{N}$

Is there any way to solve this problem using the diagonalization method? I know there's the proof that uses $\mathcal{P}(\mathbb{N})$ = set of all finite subsets $\cup$ set of all infinite subsets, ...
1
vote
1answer
27 views

What is the Church-Turing thesis?

Every source I look at online says something vague about Church's notion being equivalent to Turing's, but what exactly is the Church-Turing thesis? As I understand, it attempts to precisely define ...
0
votes
1answer
44 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
39 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
158 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. ...
2
votes
1answer
45 views

Which primepowers can divide $3^k-2$?

I tried to get a survey which primepowers $p^n$ divide $3^k-2$ for some natural k. PARI has a function znlog, but there are some issues : Instead of returning 0, if the discrete logarithm does not ...
1
vote
2answers
51 views

Finding a real number c for polynomial (proof)

The question is to find a real number c for which $ x\ge c%+$ implies $$x^4-4x^3+7x-9 \ge1000$$. I was given the hint that $x>10$, then $4x^3<0.4x^4$, so $x^4-4x^3>0.6x^4$. Problem is, I'm ...
1
vote
1answer
46 views

Math Proof Question similar to reverse triangle inequality

Prove that for any real three numbers x,y,z, $$ |x-y||z| \le |y-z||x| + |z-x||y|$$ I am way overthinking this, there must be an easier solution to this. Any thoughts?
4
votes
3answers
106 views

Show that $S=\frac{1}{a_1}+\cdots+\frac{1}{a_n}$ is not an integer.

So I have a bunch of integers $a_1,...,a_n$ and a prime number $p$ that divides only one of the numbers in this sequence, say $a_k$ I want to show, that $S=\dfrac{1}{a_1}+\cdots+\dfrac{1}{a_n}$ is ...
1
vote
1answer
27 views

Largest K-multiple free set out of a fully ordered set

i'm struggling conceptually with this problem, i don´t know how to approach it in a clever way (without a computer, or at least without a brilliant algorithm). Mathematicians defined a k-multiple set ...
1
vote
2answers
88 views

If $7$ is the first digit of $2^n$, what is the first digit of $5^n$?

Let $2^n = 7\cdot 10^x + p$ and $5^n = a\cdot 10^y + r$ And now what? (We're in base $10$)
0
votes
2answers
60 views

Fact About Equality Proven by Euler in 1748 (Context: Integer Partitions)

I'm currently reading Integer Partitions by Andrews and Eriksson. In the introductory chapter (p.2), there is the following statement: ... The table would have a more efficient design: ...
70
votes
14answers
7k views

Infiniteness of non-twin primes.

Well, we all know the twin prime conjecture. There are infinitely many primes $p$, such that $p+2$ is also prime. Well, I actually got asked in a discrete mathematics course, to prove that there are ...
4
votes
4answers
133 views

Solve $x^2+x+3=0$ mod $27$

I was preparing for my Number Theory class for next semester and one of the questions that I came upon is to solve $x^2+x+3=0$ mod $27$. I have seen modular arithmetic before but never one that ...
0
votes
1answer
58 views

Finding the private key: Attack against El Gamal

El Gamal encryption involves picking $(p,g,b)$ which is our public key. We compute $b=a^x$ $mod$ $p$. Here, $x$ is the private key which we don't know. What are some efficient and strong algorithms ...
0
votes
1answer
39 views

Proving true or false based on discrete math

Discrete math practice problems prove whether true or false If $a^2$ divides $b^2$, then $a^3$ divides $b^4$ I think it is false because it is true that if $a^2$ divides $b^2$ then $a$ divides $b$ ...