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

learn more… | top users | synonyms

0
votes
0answers
6 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 ...
1
vote
1answer
20 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
2answers
45 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 ...
1
vote
1answer
17 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$) ...
3
votes
2answers
189 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$ ...
0
votes
0answers
28 views

Explanation of a proof of the existence of reclusive primes

The goal is to prove: For any given number $N$, there exists a prime number that is at least $N$ greater than the previous prime number and at least $N$ smaller than the following one. We call those ...
7
votes
4answers
370 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
25 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
45 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
24 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
18 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
0answers
17 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
26 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
40 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
55 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
112 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
33 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
69 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
84 views

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

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
46 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
76 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
38 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
38 views

gcd and lcm from prime factorization proof [on hold]

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 ...
3
votes
0answers
64 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 ...
1
vote
4answers
67 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
29 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
59 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
12 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
49 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
33 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!
1
vote
1answer
26 views

Another exercise in number theory

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
41 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$$
3
votes
2answers
83 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
40 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 ...
4
votes
4answers
216 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
61 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?
6
votes
3answers
118 views

$x^p - 1$ always have a factor congruent to $1$ modulo $p$? [on hold]

I was doing some group theory analysis and found the above statement. can you disprove it? I am not sure with my work, I am new with Group Theory. p is an odd prime [Editor's Comment] My ...
2
votes
2answers
29 views

Question regarding n consecutive positive integers

Prove that for any positive integers $m$ and $n$, there exist a set of n consecutive positive integers each of which is divisible by a number of the form $a^m$ where a is some integer in $\mathbb ...
2
votes
4answers
70 views

Prove that $133$ divides $11^{n+1} + 12^{2n−1}$ for all $n > 1$? [duplicate]

I have tried this question so hard but still stuck here. It seems like easily provable if all $n$ are all positive numbers but in this question, the $n$ is bigger than $1$. original question : prove ...
0
votes
0answers
24 views

Another question/observation about Mersenne numbers and Euler's totient function

This is a follow up to this question Upper bound for Euler's totient function on composite Mersenne numbers and an ongoing project with lots of questions related to Mersenne numbers. I'm sorry if ...
0
votes
0answers
24 views

Counting/bounding number of relatively prime pairs?

I'm wondering if anyone knows of results counting or bounding the number of relatively prime pairs in two subsets of positive integers. In particular: Given $A = \{a \in \mathbb{Z} | m_1 \leq a \leq ...
1
vote
1answer
48 views

In how many ways can a number be expressed as a sum of squares of two natural numbers? [duplicate]

In how many ways can $145^2$ be expressed as sum of two squares? I tried solving it by finding out the Pythagoren triplets. $145= m^2+n^2 = 12^2+1^2$ & $9^2+8^2$ so triplet is $(145, m^2-n^2 , ...
1
vote
1answer
29 views

greatest common divisor and solution in integers

The greatest common divisor of 203 and 147; $gcd(203,147)=7$. Thus how can we find all the solution in integers $x,y$ of the equation $203x + 147y=7$?
0
votes
1answer
61 views

lifting the exponent lemma for $p=2$.

I am trying to understand the proof of theorem 3 (in p.4) of http://www.artofproblemsolving.com/Resources/Papers/LTE.pdf However, I dont understand the last sentence "This means the power of $2$ in ...
2
votes
1answer
69 views

Proving a set of numbers has arithmetic progressions of arbitrary length, but none infinite

For each real number $x$, let $[x]$ be the largest integer less than or equal to $x$. For example, $$[5] = 5$$ $$[7.9] = 7,$$ and $$[−2.4] = −3.$$ An arithmetic progression of length $k$ is a ...
1
vote
4answers
44 views

$ab\equiv 1\pmod{m} \implies a^q\not\equiv 0\pmod{m}$?

Let $a,b,q,m$ positive integers. Assume that $ab\equiv 1\pmod{m}$. Is it true that $a^q\not\equiv 0\pmod{m}$? My approach: If $a^q\equiv 0\pmod{m}$, then $a^qb\equiv 0\pmod{m}$ and so $0\equiv ...
-1
votes
0answers
44 views

Prove that $\gcd(a+b+c,abc)>1$ [closed]

$a,b,c$ are positive integers such that $\frac{a^3+b^3+c^3}{abc}$ is integer. Prove that if $a,b,c>1$ then $\gcd(abc,a+b+c)>1$.
0
votes
1answer
29 views

Solution to Diophantine equation with constraint.

solve the following equation over $z_x,z_y$ \begin{align} &az_x=bz_y\\ &\text{s.t. } a,b,z_x,z_y \in \mathbb{Z} \text{ and } 1 \le z_x \le N \text{ and } 1 \le z_y \le N \end{align} How ...
4
votes
1answer
47 views

Find integral solutions for $2x^2+y^2=2\times(1007)^2+1$

Find integral solutions to the equation $$2x^2+y^2=2\times(1007)^2+1$$ I tried: I rewrote the equation as $2x^2+y^2=2028099$. I found that $y_{max}=1424$ and $y$ must be odd, so I set ...