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

learn more… | top users | synonyms

0
votes
1answer
268 views

Sum of two squares [duplicate]

Possible Duplicate: Prove that $n$ is a sum of two squares? I was reading this and began wondering if there is a general theorem that a number of a given form is the sum of two squares. I ...
3
votes
4answers
141 views

what are linear divisors of integer powers?

I have been trying to prove that $n^4$ is eithere divisible by $5k$ or $5k+1$, couldn't help wonder if there is a more general theme to try later , namely if it is true that $n^m$ is divisble by at ...
4
votes
2answers
4k views

Rational Numbers - LCM and HCF

I was reading a text book and came across the following approach to find the LCM and HCF of rational numbers/fractions: LCM of fractions = LCM of numerators/HCF of denominators HCF of fractions = ...
4
votes
3answers
286 views

For integers $a$ and $b$, $ab=\text{lcm}(a,b)\cdot\text{hcf}(a,b)$

I was reading a text book and came across the following: Important Results (This comes immediately after LCM:) If 2 [integers] $a$ and $b$ are given, and their $LCM$ and $HCF$ are $L$ and ...
8
votes
2answers
249 views

Finding a Fermat number with a given prime factor

It is known that if a Fermat number $F(n) \triangleq 2^{2^n} + 1$ is composite, then every one of its prime factors can be written as $$p = 2^{n+2}k + 1\;,$$ for some positive integer $k$. Since $p ...
0
votes
2answers
155 views

Help finding what prime numbers satisfy this condition

Given: ns_num(n, seed, modulo, incrementor) = (seed + n * incrementor) % modulo n is in range $[0,10000000)$ What value of ...
6
votes
1answer
174 views

How to study results of Diophantine equation?

I finally managed to learn a bit of number theory and Diophantine equation(with the help of Arturo Magidin's great answer in what type of math is this?). But I'm wondering what's the next step after? ...
2
votes
1answer
501 views

Interesting problem on “neighbor fractions”

This is from I. M. Gelfand's Algebra book. Fractions $\displaystyle\frac{a}{b}$ and $\displaystyle\frac{c}{d}$ are called neighbor fractions if their difference $\displaystyle\frac{ad - bc}{bd}$ ...
7
votes
2answers
287 views

On natural solutions of the equation $y^{3}-3^{x}=100$

How can I solve the equation $$y^{3}-3^{x}=100$$ over positive integers?
4
votes
3answers
250 views

Properties of the prime numbers?

Consider the following exercise: Let $P_1$ be the set of all primes, $\{2,3,5,7,\cdots\}$, and for each integer $n$, let $P_n$ be the set of all prime multiples of $n$, $\{2n,3n,5n,7n,\cdots\}$. ...
1
vote
3answers
233 views

Number of factors of Carmichael numbers

Hello world! Now I'm implementing a stochastic (k-rounded) Fermat primality test for my annual scientific work. I know it is ...
8
votes
2answers
859 views

Help with olympiad question: Solve $x^3 + y^3 + z^3 = 2011 \text{ for }x,y,z \in \mathbb{Z}$

Solve the equation: $x^3 + y^3 + z^3 = 2011$ in integer numbers. I'm trying to solve problems I couldnt on the competition itself but I'm totally stuck.
17
votes
1answer
558 views

Primes of the form $x^2 +ny^2$ where swapping $x$ and $y$ still gives a prime

I am studying primes of the form $x^2+ny^2$, and i was wondering if there are any known results about the primes of this form such that when you swap $x$ and $y$ you also get a prime. ie for ...
0
votes
5answers
148 views

Is it possible to solve this system?

Given $x=4a+3 \text{ and } x=7b+6,\;\; x,a,b \in \mathbb N,\;\; x,a,b > 0,\;$ find the minimum value for $x$. How can I solve this system, given three unknown variables but only two ...
4
votes
4answers
1k views

Proving an integer $3n+2$ is odd if and only if the integer $9n+5$ is even

How can I prove that the integer $3n+2$ is odd if and only if the integer $9n+5$ is even, where n is an integer? I suppose I could set $9n+5 = 2k$, to prove it's even, and then do it again as ...
6
votes
0answers
328 views

On the equation $m^3-m^2+1 = n^2$

(i) How can I find all positive integers $m$ such that $m\equiv 4 \pmod 7$ and $m^3-m^2+1$ is a perfect square? (ii) Is there a method to solve this equation over positive integers: $$m^3-m^2+1 = ...
-2
votes
4answers
392 views

Golden ratio powers tend to integer values

If $G$ is the golden ratio, then $\lim_{n \to \infty}G^n$ tends ever nearer to integer values that approach $\infty$. Can it therefore be proved that $\infty$ is itself an integer? If not, why not?
43
votes
4answers
2k views

How to understand and appreciate the prime number industry?

Why would I want to buy prime numbers? There is a website (found it!) selling a table of 400 digit primes for twenty dollars. Like an updated version of this. I have a layman's idea that prime numbers ...
2
votes
0answers
201 views

Approximate irrational number using convergents of continued fractions

I would really appreciate it if anyone could help me with this problem: Among the convergents of $\sqrt{15}$, find a rational number that approximates $\sqrt{15}$ with accuracy to four decimal ...
3
votes
1answer
83 views

$p$-adic closures of infinite sets

Let $S\subsetneq\mathbb{Z}$ be an infinite set. Does there always exist a prime $p$ such that the closure of $S$ in the $p$-adic integers, $\mathbb{Z}_p$, contains a rational integer $n\notin S$? ...
8
votes
3answers
1k views

What is the greatest integer that divides $p^4-1$ for every prime number $p$ greater than $5$?

What is the greatest integer that divides $p^4-1$ for every prime number $p > 5$? This was on a practice math GRE so it's probably really easy.
25
votes
2answers
1k views

Proof of recursive formula for “fusible numbers”

The set of fusible numbers is a fantastic set of rational numbers defined by a simple rule. The story is well told here but I'll repeat the definitions. It's the formula on slide 17 that I'm trying to ...
4
votes
4answers
1k views

If $a|b$ and $c|d$, then $ac|bd$

I just need to check the reasoning in my proof is correct, I think it is valid although I'm not totally convinced because I can't follow the logic; does proving that $x$ is an integer prove that ...
5
votes
3answers
103 views

For what $a$ and $b$ is $9x^4-12x^3+28x^2+ax+b$ a perfect square?

If $9x^4-12x^3+28x^2+ax+b$ is a perfect square, find the value of $a$ and $b$. This is one of my past year examination's questions, some help on it? (The answer for this problem is $a=-16$, $b=16$.)
0
votes
3answers
1k views

Extract a Pattern of Iterated continued fractions from convergents

I have been working on an article at https://oeis.org/wiki/Table_of_convergents_constants where I posted a table of "convergents constants" (defined at https://oeis.org/wiki/Convergents_constant) ...
4
votes
1answer
155 views

Specific ten digit number

I'm trying to solve this little problem. So far no luck. Could anyone help? Thanks in advance :) What is the ten digit number such that the i-th digit is the number of i's in the number ( 0<= i ...
2
votes
2answers
150 views

Raising the floor function to a power

I've made a few plots and noticed that $\lfloor Is it true that for positive $x > 1$ and $n \in \mathbb N,\quad n>=2$ the following holds: $$(\lfloor x \rfloor + 1)^n >= \lfloor x^n ...
5
votes
1answer
158 views

Are all non-squares generators modulo some prime $p$?

If $q\in\mathbb{Z}^+$ is not a perfect square, does there always exist an odd prime $p$ such that $q$ is a generator of $\mathbb{Z}/p\mathbb{Z}^\times$? Can we find always find infinitely many such ...
3
votes
2answers
140 views

Calculate max/min of $x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$

What is a good way to calculate max/min of $$x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$$ where $x_1+y_1+z_1+w_1=a$ and $x_2+y_2+z_2+w_2=b$ and $x, y, z, w, a, b \in \mathbb{N} \cup \{0 \}$, and please explain ...
5
votes
1answer
207 views

Concerning: presentations of rational numbers into sums

Problem: Prove that all positive rational numbers can be expressed as the finite sum of different numbers $\displaystyle \frac {1} {n}$ ($n$ is a natural number). Example: $\displaystyle \frac ...
7
votes
1answer
238 views

What causes the convergence of Iterated continued fractions from convergents?

Here is a small discovery I stumbled across a few weeks ago. I hope at least one person will find it interesting enough to help me. The iterated continued fractions from convergents (or convergents ...
9
votes
1answer
305 views

Show that $\gcd(a_{n+1},a_n) > a_{n-1}$ implies $a_n \geq 2^n$

Let $(a_{n})$ be an infinite sequence of positive integers such that $ \gcd(a_{n+1},a_{n}) > a_{n-1} $ for all $ n\geq 1$. How do I prove that $a_{n} \geq 2^{n}$?
2
votes
2answers
1k views

Two sets of 3 positive integers with equal sum and product

Provide 2 different sets of 3 unique positive integers whose products are the same and the sums are also the same, with each number strictly between 2 and 18. Edit: Provide $\{A, B, C\}$ and ...
2
votes
2answers
75 views

Power equivalence in a prime modulus

Given, $p,q$ primes, $x$, $c$, $(p-1)/c$ integers and $$x^{(p-1)/c} \equiv 1\pmod{p}$$ how can I show there exists a $q$ such that $$q^c \equiv x\pmod{p}$$
13
votes
1answer
792 views

Is there a prime number between every prime and its square?

For each prime number $p$, is there always an other prime number between $p$ and $p^2$ ? I tested it for prime numbers $< 500,000,000$, but I wanted to know if there is any mathematical proof of ...
10
votes
1answer
299 views

Primes of the form 1..1

For $n \ge 1$ an integer, let's denote $u_n = \sum_{k = 0}^{n-1} 10^k$ That is $u_1 = 1$, $u_2 = 11$, $u_3 = 111$, $u_4 = 1111$, ... My question is the following : Which of them are prime numbers ? ...
6
votes
2answers
4k views

Extended Euclidean algorithm with negative numbers

I feel very sorry for asking probably simple and stupid questions on such a site, but a reasonable justification may be that smart answers to stupid questions will vaporize stupidity in the end and ...
6
votes
8answers
458 views

Divisibility of 9 and $(n-1)^3 + n^3 + (n+1)^3$

Question: Show that for all natural numbers $n$ which greater than or equal to 1, then 9 divides $(n-1)^3+n^3+(n+1)^3$. Hence, $(n-1)^3+n^3+(n+1)^3 = 3n^3+6n$, then $9c = 3n^3+6n$, then ...
2
votes
1answer
509 views

Good book resources (not websites) to learn number theory on my own? [duplicate]

Possible Duplicate: Undergraduate/High-School-Olympiad Level Introductory Number Theory Books For Self-Learning I took number theory this semester and loved it but don't feel like I learned ...
0
votes
2answers
428 views

Questions about algebraic identities

When people talk about algebraic identities, such as in A Collection of Algebraic Identities, are those variables appearing in them varying in $\mathbb{R}$, $\mathbb{C}$ or some even more general set? ...
4
votes
2answers
198 views

Is prime number defined to be some natural number or integer

In number theory, is prime number usually defined to be some natural number or some integer, i.e., must it be positive or can it be either positive or negative? Thanks and regards!
6
votes
5answers
710 views

Can this number theory MCQ be solved in 4 minutes?

The Problem: ( 270 + 370 ) is divisible by which number? [ 5, 13, 11 , 7 ] Using Fermat's little theorem it took more than the double of the indicated time limit. But I would like to solve it quickly ...
1
vote
2answers
112 views

Are there any non-trivial rational integers in the $p$-adic closure of $\{1,q,q^2,q^3,…\}$?

If $p$ is prime and not a divisor of $q$, are there any non-trivial rational integers in the $p$-adic closure of the set or powers of $q$? Edit: $q$ is also a (rational) integer, not a $p$-adic.
3
votes
1answer
149 views

The form $xy+5=a(x+y)$ and its solutions with $x,y$ prime

In another question I was asking if there are any different $x,y>2$ primes such that $xy+5=a(x+y)$. Where $a=2^r-1$, and $r>2$. I was thinking if it is able to find a Pell equation or a ...
0
votes
1answer
270 views

How can I find all increasing sequences $\{a_i\}_{i=1}^{\infty}$ such that $d(x_1+x_2+\cdots+x_k)=d(a_{x_{1}}+a_{x_{2}}+\cdots + a_{x_{k}})$?

How can one find all increasing sequences $\{a_i\}_{i=1}^{\infty}$ such that $$d(x_1+x_2+\cdots+x_k)=d(a_{x_{1}}+a_{x_{2}}+\cdots + a_{x_{k}}),$$ holds for all $k$-tuples $(x_1,x_2,\cdots,x_k)$ of ...
5
votes
4answers
403 views

Show that $q(n)=11n^2 + 32n$ is a prime number for two integer values of $n$

Let $n$ be an integer and show that $q(n)=11n^2 + 32n$ is a prime number for two integer values of $n$, and is composite for all other integer values of $n$.
0
votes
2answers
74 views

Back substitute example

$$ 3f + 280y = 1 $$ euclidean algorithm $$ 280 = 3\cdot 93 + 1 $$ $$ 3 = 1 \cdot 3 $$ Back sub $$ 1 = 280 + 3(-93) $$ my question is why a negative sign for 93? since in the euclidean ...
5
votes
1answer
240 views

How to find the number of continued fraction from a periodic representation?

Problem Find the number that represented by $[2,2,2 \ldots]$ I know it wasn't difficult, but I was absent the last two classes. So I just want to make sure that I got it right. My attempt was, ...
3
votes
1answer
143 views

How to find continued fraction of the form $a\sqrt{b}$?

For the form $\sqrt{b}$, I could just apply the recursive quadratic formula: $$P_{k+1} = a_kQ_k - P_k$$ $$Q_{k+1} = \dfrac{d - P^2_{k+1}}{Q_k}$$ $$\alpha_k = \dfrac{P_k + \sqrt{d}}{Q_k}$$ ...
3
votes
2answers
403 views

Infinitely many primes in the ring of integers for any quadratic field

If $d$ is an integer, not a perfect square, and $K=\mathbb{Q}(\sqrt d)$; if $\mathcal{O}_K$ is the ring of integers $K$, then I want to prove that there are infinitely many primes in $\mathcal{O}_K$. ...