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

learn more… | top users | synonyms

0
votes
0answers
39 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
403 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
35 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
50 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
25 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
25 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
21 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
41 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
58 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
117 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
38 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
74 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
100 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
56 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
81 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
44 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
58 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 ...
3
votes
0answers
71 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
77 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
38 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
66 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
15 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
37 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
28 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
43 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
154 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
41 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
228 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
74 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
122 views

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

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
30 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
82 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
29 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
27 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
51 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
31 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$?
1
vote
1answer
92 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
84 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
47 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 ...
0
votes
1answer
51 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
50 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 ...
1
vote
2answers
45 views

Given a Pell solution $(u_k,v_k)$, is there a closed form “descent” to $(u_{k-1},v_{k-1})$?

Given: a solution $(u_k,v_k)$ to the Pell equation $$U^2-dV^2=1, \qquad(\star)$$ where $d$ is a non-square integer, and $k \ge 1$ is an arbitrary integer. There are well-known recurrences to ascend ...
1
vote
7answers
53 views

$\operatorname{gcd}(ab,a+b)=1$ if $a$ and $b$ are relatively prime

I'm trying to show that if $\operatorname{gcd}(a,b) = 1$, then $\operatorname{gcd}(ab,a+b)=1$. I've tried to use the gcd properties: $$\operatorname{gcd}(a,b)=1 \implies ...
2
votes
1answer
66 views

Prove $ x^n-1=(x-1)(x^{n-1}+x^{n-2}+…+x+1)$

So what I am trying to prove is for any real number x and natural number n, prove $$x^n-1=(x-1)(x^{n-1}+x^{n-2}+...+x+1)$$ I think that to prove this I should use induction, however I am a bit stuck ...
1
vote
2answers
59 views

$2p-2$ as the sum of consecutive prime numbers

Progress: Let $p$ be a prime such that $p≡1$ (mod 6) then $2p-2$ can be written uniquely (up to the order of addends) as the sum of some consecutive prime numbers. These are first ten examples: ...
1
vote
1answer
49 views

Residue class of a huge repunit modulus a huge number

Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want ...
0
votes
1answer
80 views

How to find out a^b^c^… mod m

I would like to calculate: abcd... mod m I know when a is coprime to m then we can easily find out the answer using Euler's totient function. But I wish to know the ideas when a is not coprime to ...