2
votes
0answers
21 views

Number of nonnegative solutions of linear diophantine inequality

Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it. Is there exists algorithm which ...
0
votes
4answers
68 views

Number theory divisibility - simple way to prove this is prime?

Suppose that $y$ is a positive integer, and $z$ is the largest factor of $y$ such that $z<y$, then let $x=y/z$. Prove that $x$ must be a prime number. Is there a simple way to solve this? It ...
3
votes
1answer
81 views

How to prove a duality about partitions of numbers?

I found the following theorem, which I think should be correct but I do not know how to prove it: Consider the set containing sums $A=\lbrace\sum\limits_{i=-a}^a iX_i\rbrace$ where $X_i$ is a ...
1
vote
1answer
26 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
0
votes
2answers
37 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
75 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
92 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
123 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
307 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
32 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
20 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
41 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
69 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
36 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
50 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
94 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
40 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
97 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
189 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
155 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
69 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
31 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
148 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
70 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
267 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
72 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
101 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
45 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
40 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
172 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
52 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
47 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
108 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
31 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
62 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: ...