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

learn more… | top users | synonyms

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
197 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$. ...
3
votes
1answer
440 views

What is the theoretical upper bound of factorion numbers?

Recently I read about factorion numbers. I understood that there are only 4 factorion numbers, but what is the theoretical range in which they can be? Is it $[0, +\infty]$ or a smaller upper range? ...
4
votes
2answers
186 views

Are there distinct primes $p,q$ satisfying $pq=(2^r-1)(p+q)-5$?

We let $p\neq q$ be odd prime numbers and $r$ be integer $>2$. Are there such $p,q$ satisfying $pq=(2^r-1)(p+q)-5$? This is clear from here that, $q(p-2^r+1)=(2^r-1)p-5$, and ...
3
votes
3answers
178 views

Real quadratic field and Pell's equation

everyone. I am having difficulties with this question. Let $K = \mathbb{Q}(\sqrt{d})$ be a real quadratic field , and $ \mathcal{O}_K$ be the ring of integers of $K$. By making use of $u$, a ...
4
votes
3answers
1k views

What is the most efficient algorithm to find the closest prime less than a given number $n$

Problem Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$. Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of ...
13
votes
3answers
483 views

Proof that $(3^n - 2^n) / n$ is not an integer, $n \geq 2$

Trying to prove that $(3^n - 2^n)/n$ is not an integer for $n\geq 2$. Was trying something along the lines of induction with: $3^{n+1} - 2^{n+1} = 2(3^n - 2^n) + 3^n \equiv 0 \mod (n+1)$ But that ...
3
votes
3answers
510 views

Is there an alternative proof for periodic expansion of decimal fraction?

I'm currently reading Elementary Number Theory and Its Applications by Kenneth H. Rosen. In chapter 12 - Decimal Fraction, he provided a proof about the period length of the base $b$ is ...
2
votes
3answers
127 views

Prove that the $\mathrm{ord}_{mn}a = [\mathrm{ord}_ma, \mathrm{ord}_na]$ where $a, m, n$ are relatively prime

Problem Prove that the $\mathrm{ord}_{mn}a = [\mathrm{ord}_ma, \mathrm{ord}_na]$ where $a, m, n$ are relatively prime. My attempt was, Let $x = \mathrm{ord}_ma$, $y = \mathrm{ord}_na$, and $z = ...
2
votes
1answer
281 views

What is the Voronoi's formula to calculate the inverse modulo m $ax \equiv 1 \pmod{m}$

I searched a bit using google but I found nothing :( ! Any information would be greatly appreciated. Thank you,
3
votes
2answers
248 views

Are there infinitely many primes and non primes of the form $10^n+1$?

Prove that there are infinitely many primes and non-primes in the numbers $10^n+1$, where $n$ is a natural number. So numbers are 101, 1001, 10001 etc.
0
votes
2answers
554 views

Problems with euclidean GCD

\begin{align} 1414 &= 888 \cdot1 + 526 \qquad(1)\\ 888 &= 526 \cdot2 + 362 \qquad(2)\\ 526 &= 362 \cdot1 + 164 \qquad(3)\\ 362 &= 164 \cdot2 + 34 \,\,\,\qquad(4)\\ 164 &= 34 ...
1
vote
1answer
70 views

Error in Bell series of arithmetic functions

I want to prove that $$\frac{n}{\varphi(n)} = \sum_{d|n} \frac{\mu(d)^2}{\varphi(d)}.$$ First clear denominators to get $$n = \sum_{d|n} \mu(d)^2 \varphi(n/d).$$ Next I replaced $\mu(d)^2$ with ...
2
votes
2answers
250 views

An Algorithm to compute the GCD of polynomials of coprime numbers?

If $(a,b) = 1$ then $(a+b,ab) = 1$. If $(a,b) = 1$ then $(a+b,a-b) = 1$ or $2$. If $(a,b) = 1$ then $(a+b,a^2-ab+b^2) = 1$ or $3$. Is there an algorithm to compute the gcd of two polynomials ...
1
vote
2answers
479 views

Euclidean algorithm to find the GCD

I have to find the greatest common divisor of $a=78$ and $b=132$. I have worked out to $$\begin{align} 132 & = 78 \times 1 + 54 \\ 78 & = 54 \times 1 + 24 \\ 54 & = 24 \times 2 + 6 \\ ...
4
votes
2answers
250 views

Pell's equation

Please help me with the following question. Thank you! We know that $D$ is a positive integer, not a square. We let $k$ be any positive integer. We need to prove that the equation $x^2 - D y^2 = 1$ ...
2
votes
2answers
524 views

Show that $x^2 - 3y^2 = n$ either has no solutions or infinitely many solutions

I have a question that I have problem with in number theory about Diophantine,and Pell's equations. Any help is appreciated! We suppose $n$ is a fixed non-zero integer, and suppose that $x^2_0 - 3 ...
5
votes
3answers
1k views

Last two digits of $2^{1000}$ via Chinese Remainder Theorem?

I bumped across the aforementioned question in my notes while studying today and I have completely forgot how to do this. I remember using CRT to solve a problem like this on one of my tests, too bad ...
2
votes
2answers
259 views

How to justify if the nth term of the sequence is even or odd?

Consider the sequence $a_n$ = $a_{n-1} \cdot a_{n-2} + n$ for $n \geq 2$ with $a_0 = 1$ and $a_1 = 1$. Is $a_{2011}$ even or odd? Please justify.
6
votes
1answer
269 views

natural numbers as direct limit

I would like to know if it is possible to write the natural numbers $\mathbb N$ as an inductive limit of finite monoids such that one recovers the natural multiplication of the natural numbers. Of ...
3
votes
3answers
196 views

Modular multiplication with machine word limitations

Imagine I have 64-bit machine and the widest integer available is 64-bit signed long. I cannot use BigInteger or similar libraries for performance reasons, and all calculations I get would me modulo ...
2
votes
1answer
895 views

Prove that $a$ is quadratic residue modulo every prime if and only if $a$ is perfect square [duplicate]

Possible Duplicate: Proving that an integer is the $n$ th power Prove that $a$ is quadratic residue modulo every prime if and only if $a$ is perfect square My attempt was, Since $a$ ...
3
votes
2answers
192 views

On integer solutions of $3(u-v)(u+v)(3u+v) = (1+2u)(1-2u+4u^2)$

How to solve the Diophantine equation $3(u-v)(u+v)(3u+v) = (1+2u)(1-2u+4u^2)$ over integers? PS. I saw it here on AoPS, but could not solve it and no one has answered there.
35
votes
1answer
825 views

Functions $f:\mathbb{N}\rightarrow \mathbb{Z}$ such that $\left(m-n\right) \mid \left(f(m)-f(n)\right)$

A long time back, I wondered what functions other than integer polynomials on $\mathbb{N}$ (or $\mathbb{Z}$) satisfied the property: $$\forall m,n: \left(m-n\right) \mid \left(f(m)-f(n)\right)$$ ...
12
votes
3answers
573 views

Prove that if $p$ is an odd prime that divides a number of the form $n^4 + 1$ then $p \equiv 1 \pmod{8}$

Problem Prove that if $p$ is an odd prime that divides a number of the form $n^4 + 1$ then $p \equiv 1 \pmod{8}$ My attempt was, Since $p$ divides $n^4 + 1 \implies n^4 + 1 \equiv 0 \pmod{p} ...
2
votes
2answers
445 views

Prove that the least quadratic non-residue modulo p is $ \leq \frac{p-1}{4}$

Problem Prove that the least quadratic non-residue modulo p is $ \leq \frac{p-1}{4}$ I've been thinking of this problem for 2 days :(, and I'm still not be able to see how to prove it. I also ...
1
vote
1answer
1k views

Question regarding the product of quadratic residue modulo $p$, $p$ is prime

Problem Prove that the product of the quadratic residue modulo $p$ is congruent to $1$ modulo p if $p \equiv -1 \pmod{4}$ and is congruent to $-1$ modulo $p$ if $p \equiv 1 \pmod{4}$. First ...
1
vote
2answers
114 views

If $x^2 \equiv a \pmod{p}$, can we use Jacobi symbol to determine the equation has solution?

To determine a quadratic congruence equation has any solution, we have to evaluate $$\bigg( \dfrac{a}{p} \bigg)$$, So can we apply the algorithm of Jacobi symbol to evaluate this? If yes, what's the ...
2
votes
2answers
696 views

How to reduce congruence power modulo prime?

If I have a congruence equation, says $$x^{15} - x^{10} + 4x - 3 \equiv 0 \pmod{7}$$ Then can I use Fermat's little theorem like this: $$(x^{6})^2 \cdot x^3 - x^6 \cdot x^4 + 4x - 3 \equiv 0 ...
2
votes
2answers
109 views

Do there exist any numbers such that any in-order combination of digits is prime (including the original number)?

I was inspired by this question, in particular, where removing any digit of a prime yielded another prime. My question is, are there any numbers that this holds true for, and will continue holding ...