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

learn more… | top users | synonyms (1)

0
votes
0answers
53 views

Positive integer solutions to $p^2 + q^2 \leq 4^k$

Earlier this evening (morning), I posted a question about showing that a finite number of dyadic squares can fill up an arbitrary proportion of the unit disk. I'm sure there are better ways to prove ...
6
votes
3answers
448 views

How prove this inequality $\sum\limits_{cyc}\frac{1}{a+3}-\sum\limits_{cyc}\frac{1}{a+b+c+1}\ge 0$

show that: $$\dfrac{1}{a+3}+\dfrac{1}{b+3}+\dfrac{1}{c+3}+\dfrac{1}{d+3}-\left(\dfrac{1}{a+b+c+1}+\dfrac{1}{b+c+d+1}+\dfrac{1}{c+d+a+1}+\dfrac{1}{d+a+b+1}\right)\ge 0$$ where $abcd=1,a,b,c,d>0$ I ...
0
votes
1answer
111 views

Prove that the Goldbach conjecture implies that for each even integer $2n$ there exist integers $n_1$ and $n_2$ with $\sigma(n_1) + \sigma(n_2) = 2n$

My try so far : If goldbach conjecture is true, then every even number can be expressed as sum of two prime numbers : $p_1 + p_2 = 2n$ How should I proceed further ?
2
votes
2answers
112 views

What is the meaning of this Wolfram Alpha result when calculating $3^p = 4^q$?

I would like to know are the some $p \in \mathbb{N}$ and $q \in\mathbb{N}$ for $3^p = 4^q$ except the trivial $p = q = 0$. So, I entered the expression into Wolfram Alpha, which returned the result ...
3
votes
2answers
85 views

$\sqrt{\frac{15}{11}}$ continued fraction

I know how to find a continued fraction representation of rationals and quadratic irrationals, but I'm not sure how to proceed with square roots of rationals. For example, I want to know how to get: ...
2
votes
1answer
76 views

solve the diophantine equation: $x^3-3xy^2=z^3$

Let $ x,y,z$ be 3 integers greater than 1,if $x$ and $y$ are relatively prime, solve the diophantine equation: $x^3-3xy^2=z^3$.
1
vote
0answers
37 views

Proof of the formula for the number of components in all partitions of a given number

I have to show that this formula is the number of components in all partitions of number $n$: $$\sum_{i=1}^{n}\sum_{j=1}^{[n/i]}\sum_{k=0}^{n-ij}A_i(k) \cdot A_{j-1}(n-ij-k)$$ $A_k(n)$ is number of ...
1
vote
1answer
56 views

When is a sum of products of positive powers of 2 and 3 divisible by $2^b-3^n$?

Here we have a really tough exercise. Find all natural solution: $$\frac{\sum\limits_{k=1}^n 2^{a_k} 3^{n-k}}{c}+3^n=2^{b} ,\quad b\geq a_n; \quad a_k, b, c ,n\in \mathbb N $$ Any ideas, hints?
4
votes
3answers
140 views

Raising $2$ to the power of $2014^ {2013}$ modulo $41$

The question is as follows: $$2^{{2014}^{2013}}$$ Determine its remainder by division with $41$. I know that I need to use $\bmod 41$ and reduce the power somehow to something that can be solved ...
0
votes
3answers
848 views

Simplifying radical expressions such as $\sqrt{80}$

I am having trouble simplifying a radical expression, such as say...$\sqrt{80}$. What I do is firstly, I do 80/2, then 80/3, then 80/4, then 80/5...etc until I find the largest number that can be ...
0
votes
1answer
28 views

How can we generate a $2$-digit number $XY$ on base $B$, such that $BX+Y=Y^X$?

For example, $25$ on base $10$ is equal to $5^2$. This should be pretty easy to solve using fairly simple arithmetic. But I'm finding it hard to generate any other solutions besides the one ...
6
votes
5answers
603 views

The number $(3+\sqrt{5})^n+(3-\sqrt{5})^n$ is an integer

Prove by induction that this number is an integer: $$u_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$$ Progress I assumed that it holds for $n$ and I tried to do it for $n+1$ but the algebra gets quite messy and ...
1
vote
3answers
69 views

If $x$ leaves remainder $2$ when divided by $8$, what will the remainder be when $x + 9$ is divided by $8$?

If the positive integer $x$ leaves a remainder of $2$ when divided by $8$, what will the remainder be when $x + 9$ is divided by $8$? I love to put stuff into algebraic equations to make life ...
1
vote
3answers
57 views

Transcendental Union Algebraic = Irrational?

It is true that $\mathbb{R} = \mathbb{Q} \bigcup \overline{\mathbb{Q}}$ where $\mathbb{R}$ is the set of real numbers, $\mathbb{Q}$ is the set of rational numbers, and $\overline{\mathbb{Q}}$ is the ...
2
votes
2answers
91 views

Solution of an equation involving even integers

If $x$ is any positive even integer $> 1$. I compute: $$ c = x + x! $$ Now assume instead $c$ (even integer) is given, and I want to get back the value $x$. Is it possible to find a simple ...
1
vote
1answer
209 views

Show that there are infinitely many integers $n$ with a given number of divisors

Show that there are infinitely many integers $n$ with a given number of divisors, but at most finitely many $n$ with a given sum of divisors. Sorry no useful attempt this time, any help on ...
0
votes
1answer
241 views

Is it possible to represent subsets of natural numbers as groups with prime generators?

I'm learning group theory and I'm trying to consider the "symmetry" of a certain group of natural numbers: Here's the idea, all natural numbers are comprised of multiples of primes. So a subset would ...
2
votes
3answers
155 views

“Descent” on binary quadratic forms?

Let's say I have the Diophantine equation $$ x^2+3n^2 = y^2+3z^2. \tag{$\star$} $$ where $n$ is a known integer, and we're trying to determine solutions in integers $x,y,z \ge 1$. Rewrite ($\star$) ...
6
votes
2answers
4k views

A number is a perfect square if and only if it has odd number of positive divisors

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it. For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ ...
6
votes
4answers
437 views

There are finitely many maps on nonnegative integers satisfying $\phi(ab)=\phi(a)+\phi(b)$

How to show that there are finitely many maps $\phi:\mathbb{N}\cup\{0\}\to \mathbb{N}\cup\{0\}$ with the property that $\phi(ab)=\phi(a)+\phi(b)$ for all $a,b\in \mathbb{N}\cup\{0\}$.
0
votes
1answer
85 views

Value of an iterated sum

I am interested in the number of function evaluations required to numerically evaluate an iterated integral of the form $$ \int_0^t \int_{t_1}^t \cdots \int_{t_{n-1}}^t f(t_1,\ldots,t_n) dt_n\cdots ...
1
vote
3answers
71 views

Subgroup of matrices exercise

Let $G=\{\left( \begin{array}{ccc}1 & b \\ 0 & a \\ \end{array} \right) : a,b \in \mathbb Z_7, a \neq 0\}$. Find the order of $G$. For each prime $p$ such that $p$ divides $|G|$, find all ...
1
vote
1answer
41 views

Even numbers and Euler's Totient Function

If $m$ is even, $m|r$ and $\phi (r) \leq \phi (m)$, prove that $r=m$. I only knew the converse is also true $\phi (r) \geq \phi (m)$ but i dont know how the condition $m$ is even is gonna help, ...
1
vote
0answers
49 views

Powerful numbers in Pell solutions (or, more generally, any Lucas sequence)

There are several definitive results regarding perfect powers in the Pell numbers — e.g., the only perfect power is $P_7=169=13^2$. On the other hand, when it comes to powerful numbers, I've only ...
0
votes
1answer
33 views

Solving a recurrence relation with absolute values in it.

The recurrence relation is: Let $\{y_{j}\}_{j\in \mathbb{N}}$ be a sequence of integers and x a real number then define: $P_{1}(x):=y_{1}+(-1)^{1}|x-y_{1}|$ and the general j-step as ...
0
votes
1answer
28 views

The number of ways to form $1110€$ using $45$ notes of $20€$ and $18$ notes of $50€$

Let 45 notes of 20€ and 18 notes of 50€, how many different forms we can have 1110€? I don't know write the congruence, I had thought the following: $$45 x \equiv 1110 \pmod{20}$$ $$18 x \equiv ...
0
votes
2answers
49 views

Count the integers between $20000$ and $30000$ that end in $39$, and end in $33$ in base $4$, and end in $37$ in base $8$

How I can calculate the integers between $20000$ and $30000$ that end in $39$, and end in $33$ in base $4$, and end in $37$ in base $8$. I think that I have to solve the system of congruences: ...
1
vote
1answer
65 views

Find $n$ between $100$ and $1000$ so that $2^n+2$ is divisible by $n$

Find $n$ such that $n$ divides $2^n + 2$. Also, $n$ should be between $100$ and $1000$. It can be easily seen that $n$ is not a multiple of $4$. By brute force I have figured out that answer is ...
3
votes
3answers
137 views

Infinitude of prime numbers

Everyone knows that there is an infinitude of primes. I know the Euclide, the Euler and the Erdos proofs. But are they the only known proofs ? I will try, here, to present a fourth one : Let the ...
2
votes
1answer
70 views

The number of divisors of any positive number $n$ is $\le 2\sqrt{n}$

How to prove that the number of divisors of any positive number $n$ is $\le 2\sqrt{n}$? I have started something like below: $$ n^{\tau(n)/2} = \prod_{d|n} d$$ But not getting ideas on how to ...
4
votes
4answers
88 views

Find the sum of the multiples of $3$ and $5$ below $709$?

I just cant figure this question out: Find the sum of the multiples of $3$ or $5$ under $709$ For example, if we list all the natural numbers below $10$ that are multiples of $3$ or $5$, we get $3$, ...
3
votes
3answers
439 views

How to prove that $\frac{a+b}{2} \geq \sqrt{ab}$ for $a,b>0$? [duplicate]

I am reading a chapter about mathematical proofs. As an example there is: Prove that: $$(1) \space\space\space\space\space\space\space\space\space\space\space \frac{a+b}{2} \geq \sqrt{ab}$$ for ...
1
vote
1answer
66 views

Order of $\{x\in\mathbb {Z}, |x|+|3x-1|<5\}$

There is a multiple choices which says what is the order of $\{x\in\mathbb {Z}, |x|+|3x-1|<5\}$? a. 1 b. 3 c. 2 d. empty I know that by considering certain cases, for example when $x<0$ or ...
6
votes
3answers
146 views

The number of positive integers whose digits are all $1$, $3$, or $4$, and add up to $2k$, is a perfect square

I have been stuck on this question for a pretty long time. My teacher says that we should find a small pattern, but I can't find one. Can anyone give me a hand? Let $b_n$ be the number of ...
3
votes
2answers
84 views

A sum of difference of floors

I have the sum ( $M$ is any integer $> 1$ ): $$ \sum_{h = 1}^{M}\left(\,\left\lfloor\, 2M + 1 \over h\,\right\rfloor -\left\lfloor\, 2M \over h\,\right\rfloor\,\right) $$ and looking for a way to ...
2
votes
2answers
807 views

gcd and lcm from prime factorization proof [closed]

How should I approach obvious proofs like these I have been trying but couldn't find an elegant way to work these. Any help is highly appreciated ! Especially looking for a nice proof/hint for ...
2
votes
1answer
209 views

Looking for help with this elementary method of finding integer solutions on an elliptic curve.

In the post Finding all solutions to $y^3 = x^2 + x + 1$ with $x,y$ integers larger than $1$, the single positive integer solution $(x,y)=(18,7)$ is found using algebraic integers. In one of the ...
2
votes
4answers
90 views

Does $(m+1) + m2 + (m - 1)2^{2} \ldots + 2^{m}$ equal something simpler?

Does $(m + 1) + m2 + (m - 1)2^{2} \ldots + 2^{m}$ equal something simpler, where $m\in \mathbb{N}$? Excuse me if it is too simple, I am bit tired. Thanks.
1
vote
5answers
111 views

If $a$ divides $bc$ and $\gcd(a,b) = d$ then $\frac a d$ divides c

I'm trying to prove that if $a$ divides $bc$ and $\gcd(a,b) = d$ then $\frac a d$ divides c. I tried using Bezout identity but couldn't get anywhere.
10
votes
5answers
2k views

Disproving the claim that the numbers 1+2+4, 1+2+4+8, 1+2+4+8+16… alternate between prime and composite

I am working through an elementary number theory book and I have come across the following problem. Show the following claims are wrong: Claim 1: The sequence 1+2+4, 1+2+4+8, 1+2+4+8+16, ...
1
vote
1answer
77 views

prime division problem

$a,b,c \in$ {0,1,2,...,9} with at least one of $a,b,c$ nonzero. Prove that the six-digit integer $abcabc$ is divisible by at least 3 distinct primes. My thinking is not to use induction as there is ...
0
votes
2answers
22 views

Reference Request for Methods of the Calculation of Order

What are the standard methods of calculation of the order modulo $n$ of an integer $a$ where $\operatorname{gcd}(a,n)=1$?
0
votes
2answers
55 views

how shall i find the $n$-th term of this,

How shall I find the $n$-th term of this: $\sqrt{1+2}$ $\sqrt[3]{1+2+3}$ $\sqrt[4]{1+2+3+4}$ $\sqrt[5]{1+2+3+4+5}$ $\sqrt[6]{1+2+3+4+5+6}$ $\sqrt[7]{1+2+3+4+5+6+7}$ all the way to ...
0
votes
1answer
42 views

Order of an integer

Why is it true that: if a has order 3 modulo p then $1+a+a^2 \equiv 0 \, \text{mod}\, p$ Thank you!
2
votes
1answer
59 views

If $g$ is a primitive root, show that $a$ is a $d$th power $\iff$ $a\equiv g^{kd}$

I wanted to ask you to help me with this exercise in numer theory. Here it is: If $g$ is a primitive root modulo $p$ and $d|p-1$, show that $g^{(p-1)/d}$ has order $d$. Show also that $a$ is a ...
0
votes
3answers
48 views

$(a, b) = (b, c) = (a, c) = 1$ implies $(c^2, ab) = (ab, a^n - b^n) = (c^2, a^n - b^n) = 1$?

Let $n \geq 3$ be an integer. If $a, b, c > 0$ are integers such that $(a, b) = (b, c) = (a, c) = 1$, is it necessary that $$(c^2, ab) = (ab, a^n - b^n) = (c^2, a^n - b^n) = 1$$
6
votes
2answers
251 views

Evaluation of the sum $\sum_{i=1}^{\lfloor na \rfloor} \left \lfloor ia \right \rfloor $

Let $a$ be a positive proper fraction and $n$ is any integer then evaluate the following sum, $$\sum_{i=1}^{\left \lfloor na \right \rfloor\atop} \left \lfloor ia \right \rfloor $$ I think that ...
1
vote
0answers
52 views

Given a Pell “solution” in [integer] polynomials, what can be said about the components?

Let $x,y$ be integers, and $f(x,y)$, $g(x,y)$, and $h(x,y)$ be polynomials in $x$ and $y$ with integer coefficients such that $$ f(x,y)^2 - g(x,y)h(x,y)^2 = 1. \qquad(\star) $$ Furthermore, assume it ...
3
votes
5answers
616 views

What is easiest way to know it the large number divisible by 57

What is the easiest way to know if large number is divisible by 57? For example, how could I deduce that 57 divides 300000177?
0
votes
2answers
88 views

Find the non-trivial solutions of the diophantine equation: $a^3+3a^2b=c^3$

If $ a$ and $b$ are co-prime integers >2, can $a^3+3a^2b$ be a cube?