1
vote
0answers
57 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
42 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$
2
votes
1answer
31 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.
1
vote
2answers
51 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
17 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
28 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
18 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
121 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
52 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
1answer
166 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
68 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
31 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
70 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
22 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
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. ...
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
45 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
42 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
97 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
22 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
86 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
51 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: ...
64
votes
13answers
6k 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
121 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
54 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
37 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$ ...
0
votes
2answers
68 views

Solution to $x^2$ mod $23=7^2$ [duplicate]

Recently, I stumbled upon this problem, Solve $x^2$ $mod$ $23 = 7^2$, both here at MSE and somewhere surfing the web. I tried to solve it but don't know how. Although I can't remember where I found ...
2
votes
1answer
135 views

Expressing a positive integer as a sum of positive integers

I am trying to find a way for the positive integers written as the sum of other positive integers.( expressed in terms of some functions) I searched a bit and I came across with Partitions But in my ...
0
votes
1answer
30 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
1
vote
1answer
27 views

Recurrence relation related proof

Find a recurrence relation for the number of ternary string that do not contain 00 or 11 .
0
votes
1answer
29 views

Valid proof regarding complexity class?

Consider $L \in BPP \cap NP$. Every string $x \in L$ can be accepted with probability 2/3 since $L \in BPP$. Every string $x \not \in L$ can be rejected with probability 1 since $L \in NP$. This is ...
0
votes
2answers
53 views

Modular Arithmatic

I have been struggling with modular arithmetic, and I would like to try and finally grasp the concept. In particular, solving problems like $7^{30}$ mod 49. I know I will have to use Fermat's Theorem ...
0
votes
2answers
50 views

Solve $3x^2+6x+5=0$ mod $89$

How do you determine whether $3x^2+6x+5=0$ mod $89$ has a solution? WolframAlpha says no such solution exists. I am really curious as to how the fate of the statement was concluded.
2
votes
1answer
83 views

Solve $x^2$ $mod$ $23 = 7^2$

What is the procedure to solving $x^2$ $mod$ $23 = 7^2$? According to WolframAlpha, there is no integer solution but I am completely confused as to what steps was taken to determine that. Before ...
1
vote
3answers
61 views

Find the rest of the division when $23^{84292}$ is divided by $7$, is the procedure and the result correct?

I want to know if the procedure I have followed in order to get the result for the next problem is correct. The problem is this: Find the rest of the division when $23^{84292}$ is divided by $7$. ...
0
votes
2answers
63 views

Proving congruent statement for a prime number $p>10$

I have the next statement that has to be proved: Let $p$ be a prime number where $p>10$. Prove that $p-2$ has an inverse module $p$, this is, a number $q$ exists where $(p-2)q \equiv 1\mod(p)$. I ...
2
votes
1answer
33 views

Solve for a variable in mod

I want to solve for $s=\frac{(M-x^y)}{r}$ mod $(p-1)$ where I know the values for $M,x,y,p,s$ but don't know $r$. How can I solve for $r$? I tried to solve for $r$ by trying to compute ...
1
vote
1answer
62 views

El-Gamal: Recovering random number r

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ ...
2
votes
2answers
65 views

Show that for any $n \in \mathbb{Z}, n^3$ is congruent to 0,1,-1 modulo 9.

Having a little difficulties with this one. Tried thinking of going down the line of even/odd proofs, but couldn't get anywhere.
1
vote
1answer
63 views

Proof related with prime numbers and congruence

How to (dis)prove this $ (n-2)! \equiv 1 \mod n$ If n is said to be a prime number. I guess we'll have to use FERMAT’S LITTLE THEOREM, and I just don't know where to start from. Thanks in advance ...
0
votes
1answer
53 views

Proofs related with odd numbers and modulo 8

In my problem I have $ s! + s^{2P} \equiv 1 \mod 8$ where $s > 4, P \geq 1, s,P \in \mathbb{Z}^+$ I tried to follow that example's logic, but I could not get a result $n^2 \equiv 1 \mod 8$ ...
0
votes
1answer
30 views

How to calculate the rest of $2^{p^r-p^{r-1}+1}$ divided by $p^r$

I have the next problem: $p$ is an odd prime number and $r$ is a natural number, $r>1$. How can I calculate the rest of the division of $2^{p^r-p^{r-1}+1}$ by $p^r$ ?
3
votes
1answer
170 views

Proving statements using Euclidean division

I have a series of statements that are proved based on the equation for Euclidean division, this is: Given two integers $a$ and $b$, with $b ≠ 0$, there exist unique integers $q$ and $r$ such ...
1
vote
2answers
73 views

Which is the mathematical theory that talks about these structures?

Let's define $\sigma(n)$ as the sum of the digits of the integer $n$ modulo $9$, having posed that $\sigma(9) = 9$. Now consider 2 number $a$ and $b$ in the set $\{1, \cdots, 9\}$. Which is the value ...
-2
votes
1answer
64 views

prime number related proof

I want to prove if following is true for every integer a,b and c $$a^2 - b^2 = cp $$ then p|(a+b) or p|(a-b) where p is a prime number. Any suggestion, help would be highly appreciated. Thanks ...
0
votes
1answer
131 views

Compute discrete logarithm

I am stuck in a problem, where i have to compute discrete logarithm without use of brute force. Here is the problem: Given is a prime number $p=21495809$. Find $x$, if $7^{x}=14750571\, mod\, p$. ...