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

learn more… | top users | synonyms

2
votes
3answers
47 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
2answers
61 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
20 views

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

There is a multiple choices which syas 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 ...
4
votes
3answers
50 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
33 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 ...
1
vote
2answers
20 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
45 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
60 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
1k 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
54 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
11 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
48 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
31 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
24 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
63 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
35 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
212 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
58 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
117 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
23 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
55 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
67 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
43 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$ [on hold]

$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
28 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 ...
1
vote
2answers
44 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
50 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
60 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 ...
0
votes
2answers
53 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
46 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
76 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 ...
0
votes
1answer
76 views

Is this real number an integer?

Is this real number : $$\Big(2+\frac{10}{9}\sqrt{3}\Big)^{1/3}+\Big(2-\frac{10}{9}\sqrt{3}\Big)^{1/3}$$ an integer ? I've tried different factorization, but nothing seems to work.
6
votes
3answers
92 views

Find the prime-power decomposition of 999999999999

I'm working on an elementary number theory book for fun and I have come across the following problem: Find the prime-power decomposition of 999,999,999,999 (Note that $101 \mid 1000001$.). Other ...
0
votes
1answer
31 views

What notation to use for a sequence of integers that end with digit 5?

I need to solve a low high school home work and I ask a question about the most correct notation. The problem is to build a set of circles with $r$ and $d$ such that $d=5, 15, 25, 35,...d_{+_1}$ and ...
1
vote
0answers
32 views

Find out the no of digits in product between some prime.

How many digits are there in? $2^{17}*3^{2}*5^{14}*7$. help me.
2
votes
1answer
63 views

Explain this generating function

I have a task: Explain equation: $$\prod_{n=1}^{\infty}(1+x^nz) = 1 + \sum_{n=m=1}^{\infty}\lambda(n,m)x^nz^m $$ $\lambda(n,m)$ - is number of breakdown $n$ to $m$ different numbers (>0) It's ...
4
votes
6answers
124 views

Why is $0^0$ undefined when $x^x=1$ as $x$ approaches $0$?

This question was born in another post available here. I believe $0^0=1$, because $x^x$ is continuous as $x$ approaches $0$. Consider $\lim_{x \to 0}x^x$. Let ...
5
votes
0answers
61 views

Find the Number of Integral Solutions

Let $k$ be an integer such that $1 \leq k \leq \left(\dfrac{p-1}{2}\right)$ for some odd prime $p$. Let $ a$ be another integer such that $1 \leq a \leq (p-1)$. Then find the number of integral values ...
-1
votes
2answers
37 views

chances of repeating numbers [closed]

What are the odds of powerball choosing the same powerball 3 times in a row. Your young and smart, I took math with Moses, and we learned how to add shekels and passed
2
votes
1answer
55 views

Hard Simultaneous Diophantine Equations

Find all positive integers $a,b,c,d,e,f$ such that : $de^2=ab^2+1$ and $df^2=ac^2+1$. I tried subtracting them, it factors quite nicely. But after that, haven't a clue. I'm not sure if it's even ...
2
votes
1answer
28 views

Help in this characterization of the gaps of the symmetric numerical semigroups

Before my question, some background: Definition 1: A numerical semigroup is a subsemigroup $N$ of the additive semigroup $\mathbb N$ of the non-negative integers such that $\mathbb N-N$ is ...
1
vote
2answers
62 views

Find all solutions to the equation $x^2 + 3y^2 = z^2$

Find all positive integer solutions to the equation $x^2 + 3y^2 = z^2$ So here's what I've done thus far: I know that if a solution exists, then there's a solution where (x,y,z) = 1, because if there ...