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

learn more… | top users | synonyms

0
votes
0answers
2 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$?
2
votes
2answers
38 views

Help proving this inequality

The question asks to proof that if "$x_1,x_2,x_3$ are positive numbers show that: $$(x_1+x_2+x_3) \left(\frac{1}{x_2}+\frac{1}{x_2}+\frac{1}{x_3} \right)\ge 9$$ I've tried to use the fact that the ...
0
votes
2answers
33 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
27 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
22 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
37 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
62 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
23 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
204 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
113 views

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

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
66 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
50 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
65 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
42 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
45 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
123 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
60 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 [on hold]

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 ...
2
votes
1answer
113 views

Are there any “obviously” true propositions in number theory?

After all efforts spent on wrong proofs of famous number theory conjectures and theorems like Goldbach's or Fermat's last theorem, could one find some simple statements (might be correct ones) whose ...
2
votes
3answers
110 views

Mathematical way to solve integer numbers $217 = (20x+3)r+x$

Is there any mathematical way to find the integer numbers that solve the following equation: $$217 = (20x+3)r+x$$
1
vote
3answers
236 views

Mersenne Numbers 1+4k

Let $M$ be the set of all $a=1+4k$, $k\geq 0$. If $a, ab \in M$ then $b$ is in $M$. It's probably really easy, I just need a hint. Thank you.
3
votes
2answers
68 views

How to prove divisibility test for $4$?

Let $n$ be an integer, $4|n$ if and only if the last two digit of $n$ are divisible by $4$. I tried to use $4|n$ implies that $n\equiv 0 \pmod4$
1
vote
1answer
29 views

Find modular inverse of a number

Recently I have read extended euclid's algorithm which is used to find out the modular inverse of a number N whith respect to MOD such that $\gcd(N,MOD)=1.$ But I have a doubt that how to find modular ...
2
votes
1answer
34 views

If $z > 3$ is an integer, is there an integer $a > z$ such that $(z-j) \mid (a-j)$ for every $1 \leq j \leq z-1$?

The question is: If $z>3$ is an integer, is there an integer $a > z$ such that $$(z-j) \mid (a-j)$$ for every $1 \leq j \leq z-1$?
1
vote
1answer
46 views

Regarding 'non-square- free ' numbers.

Call an integer 'n' that is not a square or a prime power or a square-free a 'square-in'.Let n be square-in. Then between n and (2 n) is there another square-in? This is a kind of 'variation' on ...
0
votes
1answer
31 views

What is an example of a positive algebraic number lacking a prime-rational factorization?

By a prime-rational factorization of a real number $x$, let us mean a pair of finite sequences $p$ and $q$ of equal length such that every $p_i$ is a prime number, every $q_i$ is a non-zero rational ...
0
votes
1answer
73 views

How would I find $n^n \pmod 5$?

I have to find the value of the remainders when $n^n$ is divided by $5$ and sum these from $1$ to $100$. So how would I find the value of $n^n \pmod 5$ for any $n$. Thank you.
1
vote
2answers
50 views

Diophantine equation with perfect squares

Find all the integer solutions of the equation: $$(n^2-4)n = 3b^2$$ Progress I tried casework based on what $n$ is modulo $3$ but it didn't work.