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

learn more… | top users | synonyms

2
votes
4answers
39 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?
4
votes
1answer
86 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
vote
2answers
33 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
37 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
13 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
39 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
51 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
18 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
35 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
57 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
41 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
65 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$ ...
7
votes
0answers
32 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
32 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
70 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
133 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
42 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
43 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
57 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
36 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, ...
2
votes
1answer
13 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
20 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
40 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
71 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
32 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
69 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
82 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 ...
3
votes
0answers
30 views

Partial sums of exponential series as a reduced fraction

The partial sum of the exponential series can be written as $$ \sum_{k=0}^n\frac{1}{k!} = \frac{nt+1}{n!} $$ When is this fraction a reduced fraction? More precisely, when does the reduced form of ...
0
votes
1answer
19 views

Factorization with a Primitive Factor of Polynomials

Question: Let $f,g\in\Bbb Q[x]$. Why is it that $\rm\color{#c00}{(1)}$ if $f$ is monic then $f=\frac{1}{a}f^*$ for some primitive polynomial $f^*\in\Bbb Z[x]$ and $a\in\Bbb Z$ ? ...
0
votes
2answers
45 views

Find the remainder if $19^{55}$ is divided by 13.

The question, as stated in the title, is Find the remainder if $19^{55}$ is divided by 13. Here is my approach for solving this problem. I know that $19\equiv6$ (mod 13), so $19^{55}\equiv ...
3
votes
2answers
64 views

How many numbers less than $x$ have a prime factor that is not $2$ or $3$

I am trying to figure out the number of integers greater than $1$ and less than or equal to $x$ that have a prime factor other than $2$ or $3$. For example, there are only two such integer less than ...
7
votes
1answer
76 views

Divisors of sequence $1!+2!+\ldots+n!$

Is the set of prime numbers which divide at least one number in the sequence $a_n=1!+2!+\ldots+n!$ finite or infinite? I try to show that it's infinite. Suppose the set is finite and consists of ...
5
votes
0answers
87 views

A set of 19 numbers that are at most 93, and a set of 93 numbers that are at most 19, have equal sumsets [on hold]

If $x_1, x_2, ..., x_{19}$ are natural numbers lower or equal than 93 and $y_1, y_2, ..., y_{93}$ are natural numbers lower or equal than 19 then there is a non zero sum of some $x_i$ which is equal ...
2
votes
3answers
96 views

Show that $\lim_{n\rightarrow\infty}{\displaystyle\sum_{i=1}^{n}{\frac{F_n}{2^n}}}=2$

I need help to show that $\lim_{n\rightarrow\infty}{\displaystyle\sum_{i=1}^{n}{\frac{F_n}{2^n}}}=2$, where $F_n$ is the n-th number in the Fibonacci sequence. I know how to prove this by putting ...
0
votes
1answer
42 views

Find conditions on $m$ and $n$ that ensure that $f$ is a bijection.

Given: $X=\{0,1,2,...,m-1\}$, $f:X\to X$, $f(x)=nx \pmod m$. Find conditions on $m$ and $n$ that ensure that $f$ is a bijection. Progress It seems that $(m,n)=1$ but I can't prove that. I tried ...
2
votes
1answer
56 views

Prove Euler's Theorem when the integers are not relatively prime

How can I prove Euler's Theorem: $$x^{\phi(m)+1} \equiv x \pmod m$$ is still true when $x$ is not relatively prime to $m$? Edit: when m=pq where p and q are distinct primes
12
votes
1answer
498 views

Can this interesting property be proven?

$$2^2+3^2+5^2+7^2+9^2+11^2=(17)^2$$ $$22^2+33^2+55^2+77^2+99^2+11^2=(143)^2$$ Also: $$22^2+33^2+55^2+77^2+99^2+121^2=(187)^2$$ $$222^2+333^2+555^2+777^2+999^2+1221^2=(1887)^2$$ ...
1
vote
1answer
20 views

A possible defining characteristic of primitive roots.

If $n$ is a primitive root $\bmod p$ ($p$ is an odd prime ) does there always exist a least residue $t$ such that $n^t \equiv t \pmod p$ ?
3
votes
1answer
36 views

How many distinct values of floor(N/i) exists for i=1 to N.

Say we have a function $F(i)=\text{floor}(N/i)$. Then how many distinct values of $F(i)$ will exist for all $0 \leq i \leq N$ e.g. We have $N=25$ then. $F(1)=25$ $F(2)=12$ $F(3)=8$ $F(4)=6$ ...
1
vote
2answers
51 views

Notation question: $\ll$

I was perusing http://mathworld.wolfram.com/HighlyCompositeNumber.html and saw the following at the end: Nicholas proved that there exists a constant $c_2>0$ such that $Q(x) \ll (\ln x)^{c_2}$. ...