# Tagged Questions

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

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 ...
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 ...
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 ?
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 ...
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: ...
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$.
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$) ...
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$ ...
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\}$.
85 views

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: ...
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 ...
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 ...
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 ...
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$, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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.
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, ...
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 ...
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$?
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 ...
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!
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 ...
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$$
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 ...
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 ...
### 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?