Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

2
votes
0answers
30 views

Equality involving gcds [duplicate]

Let $a, m, n$ be positive integers with $a > 1$. I have to prove: $\gcd(a^m - 1, a^n - 1) = a^{\gcd(m,n)} - 1$ I would like a HINT how to continue, please. My work so far: I'm trying to prove ...
2
votes
1answer
22 views

Proof, that every nonempty set of integers, not all zero, has a greatest common divisor

I'm searching for a proof or (better) a way to understand the proof from the book "Elementary methods in number theory", that every nonempty set of integers, not all zero, has a greatest common ...
-1
votes
0answers
32 views

About an unpredictable sequence of primes [duplicate]

Let $p_n$ denote the sequence of prime numbers, with $p_0=2$. The obvious fact that the sequence $p_n$ is unpredictable is very known. I am asking if there is a mathematical proof for this. Or, this ...
4
votes
1answer
1k views

How to find in which number base the operation was done by looking at the corresponding operation in decimal system?

$$23 + 25 = 51 $$ What base is used in the above addition operation ? I have 2 methods to do this Method 1 : Through equations assume base be a $$23_a + 25_a = 51_a $$ $$2a + 3 + 2a + 5 = 5a +1 ...
2
votes
0answers
35 views

Integer $m$ such that $2^m\equiv\pm 1\pmod{2n+1}$

Let $n$ be a positive integer. Does there always exist a positive integer $m\leq n$ such that $2^m\equiv\pm 1\pmod{2n+1}$? It is true that $2^{\phi({2n+1})}\equiv 1\pmod{2n+1}$. If $2n+1$ is prime, ...
3
votes
2answers
153 views

Contradiction on prime decomposition

Take $n = 12$ $12$'s prime factorization is $2^1\times2^1\times3^1$ So then, the number of factors by UFT is $(1+1)(1+1)(1+1) = 8$ But there's only $1,2,3,4,6,12 = 6$ factors!! Where are the other ...
5
votes
5answers
64 views

$x^2-y^2=2s$, s cannot be an odd integer

How can we prove that if $x^2-y^2=2s$ holds, s cannot be an odd integer. What theorem in number theory should we use?
6
votes
1answer
34 views

Generating mirror numbers

(This was a question asked by my dear little 10 year old brother.) Let's define some kind of algorithm, where we take a number, reverse its digits, and add it to the original, and iterate until we ...
6
votes
1answer
37 views

Multiplicative structure without unique prime factorisation

The subset $N:=\{3n+1\colon n\in\mathbb{N}\}$ is closed under multiplication. 4, 10 and 25 are prime numbers in $N$. We have $100=4\cdot 25=10\cdot 10$, hence factorisation with prime numbers in $N$ ...
6
votes
2answers
138 views

Prove that the elements of the triangle sum have even numbers of divisors.

Consider the sum $$S = \sum_{k=1}^n k$$ As I was computing the first triangle number with over 500 divisors (Project Euler), I came across the hypothesis that most triangle numbers have an even ...
8
votes
2answers
253 views

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? ...
4
votes
2answers
132 views

Is every sufficiently large positive integer of the form $ab + ac + bc + 1$?

Is every sufficiently large positive integer $A$ of the form $ab + ac + bc + 1$ where $a,b,c$ are some positive integers larger than some given positive integer $d$ ? How large is sufficiently ...
-1
votes
2answers
92 views

Show the sum is equal to a product of six primes

On a set of math challenges, one of them is to prove that $$145678+456781+567814+678145+781456+814567$$ is the product of six different primes. This sounds like number theory to me, but I have no ...
7
votes
1answer
49 views

Remainder when dividing by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$

Given a $54$-digit number consisting of only ones and zeros. Prove that the remainder when dividing this number by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$. The number can be written ...
1
vote
1answer
29 views

Lehmer's conjecture/Lehmer's totient problem

I came across Lehmers problem in Wikipedia and do not grasp why it may be of any interest. Are there any serious consequences or insights if it is really confirmed ? I suppose people who struggle(d) ...
8
votes
5answers
188 views

If $(m,n)\in\mathbb Z_+^2$ satisfies $3m^2+m = 4n^2+n$ then $(m-n)$ is a perfect square.

I came across this question on another forum. The question is: $$ \text{If $m,n\in \mathbb{Z}_+$ such that $3m^2+m=4n^2+n$, then $(m-n)$ is a perfect square.}$$ I have managed to partially prove ...
4
votes
1answer
70 views

What motiveted Gauss to formulate his theorem on quadratic reprocity?

Im trying to connect his work on quadratic reciprocity with some simple question, like solution to certain diophantine equation or representing primes. Any ideas? I find it hard to imagine that he out ...
2
votes
2answers
45 views

Discrete Math Proof Method

Give a direct proof of the fact that $a^2-5a+6$ is even for any integer $a$. Suppose $a$ and $b$ are integers and $a^2-5b$ is even. Prove that $b^2-5a$ is even.
3
votes
1answer
54 views

What is an insightful proof ( not a verification ) of the Quadratic Reciprocity Law?

Helmut Koch wrote in "Introduction to classical mathematics" (Springer, 1986) about the Quadratic Reciprocity Law: "... Altogether Gauss gave seven proofs of this theorem, however they should all be ...
4
votes
1answer
26 views

Sequences that misses exactly the Polygonal and the $n$-th power numbers

Can you give an example any such sequence $u_n$ such that it misses exactly the Polygonal Numbers, say for example misses exactly the Pentagonal Numbers and so on? Can you give an example any such ...
2
votes
0answers
13 views

Distinct integers with $a=\text{lcm}(|a-b|,|a-c|)$ and permutations

Do there exist three pairwise different integers $a,b,c$ such that $$a=\text{lcm}(|a-b|,|a-c|), b=\text{lcm}(|b-a|,|b-c|), c=\text{lcm}(|c-a|,|c-b|)?$$ None of the integers can be $0$, because the ...
2
votes
2answers
50 views

If $\gcd(a,n)=1$ then there exist integers $x,y$ such that $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y \pmod n$

If $a$ is integer and $n$ is positive integer such that $\gcd(a,n)=1$ then there exist integers $x,y$ for which $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y\pmod n$. By Dirichlet's principle I ...
2
votes
1answer
334 views

Theorems similar to Euler's theorem ($a$, $n$ are not coprime)

It is well known that if $\gcd(a,n)=1$, then $a^{ϕ(n)}=1$ mod $n$. Are there any results similar to Euler's theorem that can be used when $a$ and $n$ are not coprime. Feel free to add any ...
4
votes
0answers
46 views

Extention of Euclid's GCD Algorithm. (The Art of Computer Programming, Volume 1, Edition 3, Section 1.2.1, Exercise 12)

Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$, needs the inputs to be positive integers. Exercise 12 provides an extension to this algorithm and allows $c$ ...
2
votes
3answers
40 views

Is $ x^n-y^n$ is a product of coprime factors?

In the expression: $x^n-y^n$, if $n>2$ and $x,y$ are relatively prime, are the factors $x-y$ and $ x^{n-1}+x^{n-2}y+.....$ always coprime? Why? Please exclude the cases where $x-y=\pm 1$ and $\pm ...
0
votes
0answers
15 views

What is the “cost” of computation of two special CAS algorithms

Suppose I have an integer $n$ with e.g. a large number of say decimal digits. I would like to get some information about the runtime "cost" of standard CAS algorithm which factors $n$ into primes ...
-5
votes
1answer
55 views

A big challenge on Number theory [on hold]

Let $N=\frac{60^{2014}}{7}$. What is the sum of the first $2014$ digit before the decimal point of $N$?
8
votes
1answer
199 views

How to solve $y^2=3x^4+3x^2+1$ for integers.

If $x,y \in \mathbb Z$ , then find all the solutions of $$y^2=3x^4+3x^2+1$$ I was asked this question by my friend who said that he encountered this while solving another problem. I have ...
1
vote
0answers
24 views

Determining the starting value for primality test

This question is about Lucasian primality test for numbers of the form $N=3\cdot 2^n-1$ . There is a following statement in Wikipedia article : Lucas-Lehmer-Riesel test : "If $k = 3$ : if $n = 0$ ...
4
votes
3answers
163 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 ...
6
votes
0answers
62 views

When can $n^k+k$ be a perfect square?

For what positive integers $k$ does there exist a positive integer $n$ such that $n^k+k$ is a perfect square? Certainly for all $k$ such that $k+1$ is a perfect square, since we can substitute $n=1$. ...
3
votes
3answers
71 views

Writing number as sum of reciprocals of factorial

Given a real number $r>0$. Is there a way to determine whether $r$ can be written as a (possibly infinite) sum of distinct terms of the form $1/n!$? For example, if we want to determine whether ...
1
vote
2answers
43 views

How prove this diophantine equation $x^2-y^2\equiv a\pmod p$ have only $p-1$roots

Question: let $a\neq 0$.and $p$ is prime numbers. show that the number of ordered two-tuples $(x,y)$such this following diophantine equation $$x^2-y^2\equiv a\pmod p$$ at most $p-1$ ...
2
votes
1answer
67 views

Find the greatest integer $N$ such that no two of its digits are equal and each digit is also its factor

$N$ is a positive integer such that no two of its digits are equal and each digit is also its factor. What is the largest value of $N$? So far, I've determined that $0$ cannot be the last digit, and ...
3
votes
1answer
36 views

Diophantine equation involving factorial …

Question . Find all positive integer solutions to the equation below , $$(n-1)!+1=n^m$$ (i)observe that $n>1$ and $n$ is a prime number (if not we can choose a prime number $p<n$ such that $p|n$ ...
-1
votes
1answer
40 views

Relations between the GCD of two numbers and the GCD of their linear combinations

(a) Prove that $a|b$ if and only if $\gcd(a,b) = a$. (b) Let $b > 9a$, Show that $\gcd(a,b) = \gcd(a,b−2a)$ (c) Show that If $a$ is even and $b$ is odd, then $\gcd(a,b) = \gcd(a/2,b)$ (d) Show ...
3
votes
1answer
42 views

What is the discrete log used for?

Perusing Wikipedia, I stumbled on the discrete logarithm. I looks interesting that we'd be able have a function that could solve $b^k=g$ for integers $b,k,$ and $g$. However, Wikipedia says "No ...
-1
votes
1answer
79 views

Prove that there are infinity many numbers you can't write in the form $a^{T(a)}+b^{T(b)}$.

Prove that there are infinity many numbers you can't write in the form $a^{T(a)}+b^{T(b)}$ where a and b are positive integers. T(a) represents the number of divisors number a has.
5
votes
1answer
66 views

Is this an accurate proof that no perfect square is of the form $4k+3$? ($k$ an integer)

A positive integer $n$ is a perfect square. Prove that it cannot be of the form $4k+3$, where $k$ is an integer. I tried to prove this by proof by contradiction: if $n$ is a perfect square, then ...
1
vote
1answer
322 views

Discriminant of a binary quadratic form and an order of a quadratic number field

Let $ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. Let $D = b^2 - 4ac$ be its discriminant. It is easy to see that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). Conversely ...
5
votes
2answers
269 views

Can both $x^2 + y+2$ and $y^2+4x$ be squares?

Prove that there exist no positive integers $x$ and $y$ such that both $x^2+y+2$ and $y^2+4x$ are perfect squares. I thought I could perhaps solve this by square bounding but I couldn't get anywhere ...
2
votes
3answers
153 views

What is the maximum difference between two successive real numbers in the given floating point representation?

The following is a scheme for floating point number representation using 16 bits. Sign :- Bit 15 Exponent:-Bit 14-9 Mantissa :- Bit 8-0 Let $s, e,$ and $m$ be the numbers represented in binary in ...
1
vote
1answer
24 views

Congruence with $x$ in a power

I don't know how to find $x$ in a situation like this: $$a^x \equiv b \pmod c$$ I think I'm missing something around little fermat theorem, Could anyone help?
3
votes
4answers
80 views

More rigorous method for this elementary problem?

The problem is: Find all real values of $x$ such that $$(5+2\sqrt{6})^x+(5-2\sqrt{6})^x=2\sqrt{3}$$ One solution I received was as follows: $5+2\sqrt{6}$ can be expressed as ...
8
votes
0answers
36 views

Divisors of sequence $n,P(n),P(P(n)),\ldots$

Let $P(x)$ be a polynomial with nonnegative integer coefficients consisting of more than one nonzero term. Let $n$ be a positive integer. Is the set of prime numbers which divide at least one number ...
5
votes
0answers
35 views

Congruence properties of $a^5+b^5+c^5+d^5+e^5=0$?

It is known that given a solution to, $$a^4+b^4+c^4 = d^4\tag1$$ then either $-c+d,\;c+d$ is always divisible by $2^{10}$. For example, $$95800^4+414560^4+217519^4=422481^4$$ then ...
2
votes
2answers
136 views

Proof by Contradiction on prime numbers [duplicate]

Prove using contradiction that any prime number greater than $3$ is of the form $6n \pm 1$. Thanks for any help
3
votes
1answer
181 views

Testing polynomial equivalence

Suppose I have two polynomials, P(x) and Q(x), of the same degree and with the same leading coefficient. How can I test if the two are equivalent in the sense that there exists some $k$ with ...
1
vote
0answers
43 views

Is there a solution to $a^4+(a+d)^4+(a+2d)^4+(a+3d)^4+\dots = z^4$?

One can be familiar with, $$31^3+33^3+35^3+37^3+39^3+41^3 = 66^3\tag{1}$$ I found, $$29^4+31^4+33^4+35^4+\dots+155^4 = 96104^2\tag2$$ which has 64 addends. The equation, ...
1
vote
2answers
103 views

Distinct Mersenne numbers are coprime

How can you prove that if $p$ and $q$ are distinct primes, then the following holds?: $$(M_p,M_q)=1$$ Note: $M_n=2^n-1$, with $n$ prime number