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

learn more… | top users | synonyms

0
votes
0answers
24 views

Residue classes numbertheory

I have to solve the following equation: $x^6 \equiv x (\textrm{mod }396)$, with $x \in \mathrm{Z}/396\mathrm{Z} $. So I rewrote this equations as the following system: $x^6 \equiv x ...
2
votes
0answers
10 views

Boundedness of $\gcd(|x-y|,|a_x-a_y|)$ in sequence

Let $a_1,a_2,\ldots$ be an infinite sequence of distinct positive integers, and let $n$ be a positive integer. Does there always exist integers $x,y$ such that $\gcd(|x-y|,|a_x-a_y|)>n$? When ...
2
votes
1answer
24 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 ...
2
votes
1answer
48 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
222 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 ...
6
votes
1answer
38 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
141 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 ...
6
votes
1answer
35 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 ...
1
vote
1answer
32 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
1answer
50 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 ...
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
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 ...
5
votes
5answers
67 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?
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
2answers
133 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 ...
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
3answers
41 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 ...
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$ ...
-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$?
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$ ...
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$ ...
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
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 ...
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
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?
-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 ...
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$ ...
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 ...
3
votes
3answers
72 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 ...
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
0
votes
1answer
12 views

Rational roots of a polynomial with integral coefficients and constant term 1.

Here is the problem I am working on from Hardy "A course of Pure Mathematics." Given the polynomial with integral coefficients $x^n+p_1x^{n-1}+p_2x^{n-2} + \cdots + p_n = 0$, with $p_n=1$, and ...
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, ...
0
votes
1answer
45 views

Find all positive integers $a,b,c,d$ with given conditions. [on hold]

Find all positive integers $a, b, c, d$ such that $$\left(1+\frac{1}{a}\right)\left(1+\frac{1}{b}\right)\left(1+\frac{1}{c}\right)\left(1+\frac{1}{d}\right)-\frac{1}{abcd}$$ is a positive integer. ...
1
vote
2answers
63 views

About the infinitude of some kind of primes? [on hold]

I will propose this proof: A Mersenne number always has the form $$2^{p}-1=4n+3$$ since for all $p≥2$ we have $$2^{p}-1≡-1(mod4)≡3(mod4)$$ The Dirichlet prime number theorem ...
2
votes
1answer
38 views

Prove that if $\{a_n\}$ is a sequence of natural numbers such that $\{ a_n^{-1}\}$ is an arithmetic sequence then all $a_i$ are equal

Prove that if $\{a_n\}$ is a sequence of natural numbers such that $\left\{\frac{1}{a_n}\right\}$ is an arithmetic sequence then all the $a_n$s are equal. I have no clue where to begin from, ...
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 ...
1
vote
1answer
18 views

Are Primitive Dirichlet Characters linearly independent.

For a positive integer $N$, let $$S_N=\{ \chi~\mid~ \chi \text{ is primitive Dirichlet characters modulo }F,\text{ where } F\mid N \}.$$ I want to check the Linear independence on $S_N$. More ...
0
votes
3answers
66 views

How do I prove that $x^2 ≡ 3 \mod4$ has no solutions? [on hold]

The congruence $x^2 ≡ 3 \mod4$ has no solutions. How do we prove that it has no solutions?
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 ...
0
votes
1answer
23 views

How to get the maximum and minimum number of length $m$ and the sum of the digits $s$

How to get the maximum and minimum of length $m$ and the sum of the digits $s$ By example: Length: 2 Sum of its digits: 15 Max: 96, Min: 69 Length: 2 Sum of its digits: 2 Max: 20, Min: 11
2
votes
2answers
41 views

When is a number square in Galois field p^n if it's not square mod p?

Here is the problem, that I'm stuck on. There is no square root of $a$ in $\mathbb{Z}_p$. Is there square root of $a$ in $GF(p^n)$? Well, it's certainly true that $$x^{p^n}=x$$ and $$x^{p^n-1}=1$$ ...
1
vote
4answers
72 views

How many cube roots does 1 have modulo 162?

How many cube roots does $1$ have modulo $162$ this is equivalent to saying how many solutions to $x^3 \equiv 1 $ mod$162$ all my attempts are leading a dead end any help appreciated the fact that ...
2
votes
1answer
33 views

Find $x$ such that $x \equiv7\pmod {37}$ and $x^2 \equiv 12\pmod {37^2}$

Find $x$ such that $x \equiv7 \pmod {37}$ and $x^2 \equiv 12\pmod {37^2})$ My attempt: Given $x \equiv7\pmod {37}$ so $37|(x-7)$ so $37^2|(x-7)^2$ so $x^2-14x+49 \equiv 0\pmod {37^2}$ as ...
1
vote
2answers
39 views

How to prove $x^{\phi(m)+1}\equiv x\pmod{p}$ [duplicate]

How do I prove that $x^{\phi(m)+1}\equiv x\pmod{p}$ when $m=pq$, two distinct primes? I kind of have an idea that it involves Euler's Theorem but it doesn't seem to be working as well as I wanted it ...
15
votes
1answer
70 views

Showing $\left(a + \frac{1}{2}\right)^N + \left(b + \frac{1}{2}\right)^N \in \mathbb{Z}$ for finite amount of natural numbers $N$

If $a$ and $b$ are positive integers, how would I go about showing that$$\left(a + \frac{1}{2}\right)^N + \left(b + \frac{1}{2}\right)^N \in \mathbb Z $$ for only a finite amount of natural numbers ...
1
vote
2answers
46 views

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod {73}$

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod{73}$. It is clear that an attempt to write this out as $90x-41=73n,\exists n\in \mathbb{Z}$ won't be very ...
7
votes
1answer
84 views

Simple Question On Relationship Between Cubes And Squares

I'm new to this number theory business, not to mention terribly naive. I wonder whether someone could explain the technique (assuming there is one) to show whether the expression $12C - 3$ (where ...
1
vote
1answer
20 views

Proving the asymptotic behavior of the prime counting function (Prop 2.1 in Ch.7 Princeton Lectures in Analysis-Complex Analysis)

This is taken from Complex Analysis by Elias M. Stein and Rami Shakarchi. $\psi(x) \text{ is Tchebychev’s ψ-function defined by}$ $$\psi(x)=\sum_{p^m\leq x} \text{log }$$ the sum is taken over the ...