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

learn more… | top users | synonyms (1)

2
votes
1answer
130 views

Fastest Way To Compute below

Below is what I need to calculate efficiently. Find the number of natural numbers which is divisor of both $N$ and $K$. Find the number of natural numbers which is divisor of $N$ and is divisible ...
2
votes
1answer
613 views

A power-exponential congruence equation

Let $n \in \mathbb{N}$ with $(n,\varphi(n))=1$ , where $\varphi$ is the Euler-totient function. Prove the equation $x^x \equiv c \pmod{n}$ has integer solution for all $c \in \mathbb{N}$ My thought: ...
2
votes
1answer
177 views

Finding the remainder

Corresponding terms from the sequence $1,2,3,4,5...$ and $2^1,2^2,2^3,2^4,2^5,...$, are multiplied, creating the sequence $1\times 2^1,2\times 2^2,3\times 2^3,4\times 2^4,5\times 2^5...$. Let $A$ be ...
2
votes
1answer
151 views

What is the smallest $k$ such that two disjoint sets remain unequal when elements are considered modulo $k$?

Let $X$ be a finite set of positive integers. Define $X$ mod $k$ as multiset of positive integers obtained by mod operation on every element of $X$. For example, $\{3, 5, 8\} \bmod 3 = \{0, 2, 2\}$. ...
2
votes
1answer
1k views

How to find integer solutions for indeterminate equations in $Ax + By = C$

I would like to find some positive integer solutions to an equation in the form $Ax + By = C.$ I have already seen some methods for doing this, such as the one outlined in this Math.SE post. What I ...
2
votes
1answer
812 views

Is Sum of digits related with Sum of Squares of its digit

In a specified range, I want to get the number of numbers, in which sum of its digits and sum of squares of its digits are prime number. For an example from 2 to ...
2
votes
1answer
63 views

Closed form for a sequence related to divisibility

If we consider intervals of the form $[1,p_k !! ]$ in which $p_k!! := 2\cdot3\cdots p_k$ we can ask about distribution of primes, near-primes, etc., on such intervals. A naive approach might be to ...
2
votes
1answer
120 views

Quadratic equation with coefficients from FLT

Let $a,b,c>0$ be pairwise relatively prime and $n>2$ be odd. Can the equation, $a^n\cdot x^2+b^n\cdot x+c^n=0$, have rational roots $x$?
2
votes
1answer
313 views

Number of primes less than 2n

A series of questions. Explanations would be useful. I have done the first four parts. I am confused on how to go about the last two. Show that for any prime $p$ the largest power of $p$ that ...
2
votes
1answer
89 views

Preceding an integer by several zeros or an infinite number of digits

Can I write the integer 2 with some zero before as : 002 Can I precede all integer by an infinity of zero : ..........002 Does it make sense to write an integer as an infinity of numerals ? For ...
2
votes
1answer
63 views

Maximising the product of exponents, but minimising the product of the base raised to its respective exponent

Given the following sequences: let value = $(b_0^{p_0})(b_1^{p_1})\cdots(b_n^{p_n})$ let productOfExponents = $p_0 \cdot p_1 \cdots p_n$ Where $p_i\geq 0$ and $p_i$ an element of $\mathbb{N}$ for ...
2
votes
2answers
251 views

If $s$ is a multiple of both $a$ and $b$, then $s$ is a multiple of $\operatorname{lcm}(a,b)$

I came across this as I was doing work for one of my classes. We just use this property, proved presumably in number theory, which we didn't need to take. Could someone help me? Prove that if $a$, $b$ ...
2
votes
1answer
211 views

How to go from Fermat’s little theorem to Euler’s theorem thought Ivory’s demonstration?

Ivory’s demonstration of Fermat’s theorem exploit the fact that given a prime $p$, all the numbers from $1$ to $p-1$ are relatively prime to $p$ (obvious since $p$ is prime). Ivory multiply them by x ...
2
votes
2answers
132 views

how to solve $\pm y \equiv 2x+1 \pmod {13}$ with Chinese remainder theorem or iterative method?

how to solve $\pm y \equiv 2x+1 \pmod {13}$ with Chinese remainder theorem or iterative method? It comes from solving $x^2+x+1 \equiv 0 \pmod {13}$ (* ) and background is following: 13 is prime. ...
2
votes
1answer
584 views

Convergent of continued fractions the best rational approximation of a number? [duplicate]

Possible Duplicate: A nicer proof of Lagrange's 'best approximations' law? I was reading through the wikipedia article on continued fractions, and they state, essentially, that ...
2
votes
2answers
563 views

Using recurrences to solve $3a^2=2b^2+1$

Is it possible to solve the equation $3a^2=2b^2+1$ for positive, integral $a$ and $b$ using recurrences?I am sure it is, as Arthur Engel in his Problem Solving Strategies has stated that as a method, ...
2
votes
1answer
402 views

Proving a Diophantine equation has no solutions

I'm trying to show that $7u^2=x^2+y^2+z^2$ has no solutions in $\mathbb{Z}$ when $u$ is odd. If $u$ is even, then it's simple to show that no solutions exists by looking modulo $4$. The odd case looks ...
2
votes
3answers
94 views

Euclidean division remainder bound

It is normally stated that for any two integers $m,n \in \mathbb{Z}$ there exist $q,r \in \mathbb{Z}$ with $m=qn+r$ where $0 \leq r < n$. Is it possible to do this with $|r|\leq \frac{|n|}{2}$ ...
2
votes
1answer
73 views

Sequence finding

Find all such sequences $(x_1, x_2, x_3, ..., x_{63})$ consisting of different positive integers that for $n=1,2,3,...,62$ the number $x_n$ is a divisor of $x_{n+1}+1$ and $x_{63}$ is a divisor ...
2
votes
1answer
54 views

Distributivity of a dot product-like operation

Let $b_1, \ldots, b_n \in \mathbb{N}$. For $x, y \in \mathbb{Z}^n$, define $x \cdot y$ as $\newcommand{\lcm}{\operatorname{lcm}}$ $$x \cdot y = \left(\sum_{i=1}^n (x_i \text{ mod } b_i)(y_i ...
2
votes
1answer
109 views

Is it possible to know if sums of powers of a number is divisible by another number?

Is there a way to find whether a number (say $A$) formed by summing powers of another number (say $B$) is divisible by another number $C$? $A$ is a number like, for example, $B^1+B^3$. We can use a ...
2
votes
1answer
162 views

Help proving two conjectures about prime factorization and the floor function

Let me first pose the questions free of context: Given prime $p$ and positive integers $b$ and $N$, define $$F(p,b,N) = \Big\lfloor (1/b) \sum_{i=1}^\infty \lfloor N/p^i \rfloor \Big\rfloor.$$ ...
2
votes
2answers
413 views

Testing pythagorean triples: $333,444,555$

In this page there is a necessary and sufficient test given for testing Pythagorean triples: A simpler, more powerful test is, (by naming the even leg a): $(c − a)$ and $\large\frac{(c − b)}{2}$ ...
2
votes
1answer
167 views

Non-negative solutions of the equation $5^n+7^m=k^3$

How can I find all triples $(m,n,k)$ of non-negative integers such that $5^n+7^m=k^3$?
2
votes
1answer
1k views

Prove that $a$ is quadratic residue modulo every prime if and only if $a$ is perfect square [duplicate]

Possible Duplicate: Proving that an integer is the $n$ th power Prove that $a$ is quadratic residue modulo every prime if and only if $a$ is perfect square My attempt was, Since $a$ ...
2
votes
1answer
105 views

Is the estimation of number's name's length and comma-grouping feasible?

I am thinking in a mathematical problem that probably is already formulated and even solved. It is about big integers and someting else. Let n be an integer positive number. For n := 1,000 we have ...
2
votes
1answer
744 views

Question regarding Hensel's Lemma

Hensel's Lemma Suppose that f(x) is a polynomial with integer coefficients k is an integers with $k \geq 2$, and p is prime. Suppose further that $r$ is a solution of the congruence $f(x) ...
2
votes
1answer
331 views

Legendre Symbol

I have a question about Legendre symbol. Let $a$, $b$ be integers. Let $p$ be a prime not dividing $a$. Show that the Legendre symbol verifies: $$\sum_{m=0}^{p-1} \left(\frac{am+b}{p}\right)=0.$$ I ...
2
votes
2answers
685 views

How to prove Lucas's Converse of Fermat's Little Theorem without using primitive root?

Problem: If $x^{n-1} \equiv 1 \pmod{n}$, and for all divisors $q$ of $n - 1$, $a^{q} \not\equiv 1 \pmod{n}$, then $n$ is prime. $(n > 1)$ I read the proof in the book and it was very ...
2
votes
1answer
36 views

How to prove the sum of squares larger than 1/n without induction? [duplicate]

known that: $1\geq R_1 \geq R_2 \geq \dots \geq R_n \geq 0$ and $\sum_{i=1}^n R_i=1$ To prove: $\sum_{i=1}^n R_i^2 \geq \frac{1}{n}$ Using induction, the problem can be easily proved. I'd like to ...
2
votes
0answers
35 views

Conjectured new primality test for Mersenne numbers

How to prove that this conjecture about a new primality test for Mersenne numbers is true ? Definition: Let $M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}}$ ...
2
votes
0answers
18 views

How to pigeonhole the primes between $p_n$ and $p_{n+1}^2$ for twin prime conjecture?

For any full list of the primes up to the $n$th prime: $P = \{2, 3,5,\dots, p_n\}$, any natural number $q$ such that $ p_n \lt q \lt p_{n+1}^2$ that is not sieved by a prime in $P$ is also a prime. ...
2
votes
0answers
32 views

$a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $.

Let $n \in Z$, $n > 1$ and let $a \in Z$ with $1 \leq a \leq n$. Prove that if $a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $. Proof: Suppose ...
2
votes
0answers
22 views

Smallest number of workers in factory, Diophantine approximation

Q. In a factory, the percentage of male workers was $53.7802\%$ (rounding to nearest fourth decimal place) last year. What is the smallest number of female workers working there? Hint: Diophantine ...
2
votes
0answers
36 views

Legendre symbol identity

I try to solve the following problems ($p$ is an odd prime) Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}{p} \right)$$ ...
2
votes
0answers
53 views

A false conjecture by de Polignac

(This question would be similar to my other on Goldbach's conjecture so I'll change the "rules") In 1848 de Polignac claimed that "every odd integer is the sum of a prime $p$ and a power of $2$". For ...
2
votes
0answers
25 views

Application of Legendre, Jacobi and Kronecker Symbols

Legendre, Jacobi and Kronecker Symbols are powerful multiplicative functions in ...
2
votes
0answers
40 views

Please help me understand Analytic Density $\lim_{\sigma \to 1^+}\frac{1}{\zeta(\sigma)}\sum_{n \in A} \frac{1}{n^{\sigma}}$

$d (A) = \lim_{\sigma \to 1^+}\frac{1}{\zeta(\sigma)}\sum_{n \in B} \frac{1}{n^{\sigma}}$ for $B \subset \Bbb{N}$. So clearly this limit is $0$ for reciprocally summable (convergent) $B$. My goal ...
2
votes
0answers
30 views

A relation related with odd perfect numbers

It is easy to prove, using the relation $\prod_{d\mid n}d=n^{\sigma_0(n)/2}$ holds for $n\geq 1$ where $\sigma_0(n)$ is the number of divisors, the following Proposition. The integer $n\geq 1$ is ...
2
votes
0answers
34 views

How many “near-Fermat triples” are there?

Is the following statement true? Claim For every $n\in \mathbb N$, there is a constant $d$ such that there are infinitely many triples $a,b,c \in \mathbb N$ with $$ | a^n + b^n - c^n | ...
2
votes
0answers
41 views

Find the smallest number $n$ such that there exist polynomials $f_{1}, f_{2},…,f_{n}$ with rational coefficients

Find the smallest number $n$ such that there exist polynomials $f_{1}, f_{2},...,f_{n}$ with rational coefficients satisfying $$x^{2}+7=f_{1}(x)^{2}+f_{2}(x)^{2}+...+f_{n}(x)^{2}.$$ It's Olympiad ...
2
votes
0answers
78 views

Is there a formula for $1+\sqrt{2}+\sqrt{3}+\cdots+\sqrt{N}$? [duplicate]

Is there a known formula to the sum $$1+\sqrt{2}+\sqrt{3}+\cdots+\sqrt{N}$$ where $N$ is some natural number? Thanks
2
votes
1answer
18 views

Necessary condition for a finite cyclic sum of length $4$ made of $1$ and $-1$ to be $0$

This is something I observed when I was reading the classic Problem-Solving Strategies by Arthur Engel. I liked the way he solved the following problem: Let $a_1,\ldots,a_n\in\{-1,1\}$ such that ...
2
votes
1answer
26 views

For any $N$ and $B$, is there always a $B$-smooth relation $x + y \equiv 0 \pmod{N}$?

Let $N$ be any integer and $B \geq 2$ be a smoothness bound. Does there always exist $B$-smooth integers $x,y$ such that: $$x + y \equiv 0 \pmod{N}\text{ ?}$$ My only progress is that I know the ...
2
votes
0answers
31 views

Generating all coprime pairs

The Wikipedia article on coprime integers has a brief section on generating all coprime pairs. All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint ...
2
votes
0answers
28 views

Finding a lower bound

Given four positive integers $n,$ $m,$ $l$ and $k \geq 2.$ I want to find a lower bound for this expression $$|\sqrt[k]{n}+\sqrt[k]{m}-\sqrt[k]{l}|$$ in terms of these integers. Many thanks
2
votes
0answers
55 views

Find positive integer $x$, $y$, $z$ such that $2x^{2x}-1=y^{z+1}$

Find all positive integer $x$, $y$, $z$ such that $2x^{2x}-1=y^{z+1}$ I have tried to use LTE lemma but it didn't work. I think my problem is $z+1$. I can not control it. When I use LTE lemma, the ...
2
votes
0answers
27 views

$x-y^4= LCM(x, y)$ [duplicate]

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with the least common multiple, but other than that, the textbook gave no hints ...
2
votes
0answers
23 views

Fast multiplication times a fixed constant $A$?

Is there a way to speed up integer multiplication of billions of $B_{i}$'s times a fixed $A$? We can configure $A$ to be either small compared to the $B_{i}$'s (e.g. $10^{10}$ compared to $10^{200}$) ...
2
votes
2answers
58 views

Sailor,Monkey,Coconut answer in elaborate

In Sailor, Monkey, Coconut Problem Can anyone tell me how adding 56 gives me another solution??I understand that cocount is divided into 5 piles.But how is 56 give me another solution?why wouldn't ...