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

learn more… | top users | synonyms (1)

1
vote
2answers
92 views

Show that $[2x]+[2y] \geq [x]+[y]+[x+y]$

Prove that $[2x]+[2y] \geq [x]+[y]+[x+y]$ whenever $x$ and $y$ are real numbers. The $[]$ symbol is the greatest integer or floor function. I have proved this fact by cases, but I stumbled upon what ...
0
votes
1answer
27 views

Quadratic congruences in which modulus is divisible by constant term

There are two similar congruences: $$ x^2-6x\equiv16\pmod{512}\\ y^2-y\equiv16\pmod{512} $$ It is easy to see that the $\gcd$ of all three parts in both of them is $16$, $x$ and $x-6$ are even and one ...
3
votes
1answer
60 views

Question about how to prove $x^5\equiv x \pmod {10}$ [duplicate]

I was trying to prove why $x^5\equiv x \pmod {10}$ for all natural numbers $x$. I saw a proof where they applied Euler's theorem to show this. They said that the totient function for $10$ is $4$. ...
0
votes
0answers
49 views

Induction: Fibonacci / Lucas Numbers [duplicate]

From Andrews' Number Theory, Chapter 1, Section 1, Problem 15: Prove, by induction, that $F_{2n} = F_nL_n$ where $F_n$ denotes the nth Fibonacci number and $L_n$ denotes the nth Lucas ...
3
votes
3answers
76 views

Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$

Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$ without the use of a calculator. It is clear that $2003^4+1$ has a $082$ at the end of its number so $2003^4+1$ only has one factor of ...
2
votes
1answer
50 views

Sum of numbers between consecutive multiple numbers of $N$ proof

I need to see if I can generalize a proof: whether the sum of all numbers between two consecutive numbers multiples of $N$, being $N$ a natural number such that $N > 2$ is a multiple of $N$. I ...
4
votes
4answers
135 views

Solve $2(x+y)+xy=x^2+y^2$ where $x,y \in \mathbb{Z}$

Solve the equation: $$2(x+y)+xy=x^2+y^2$$ How should I go about solving this? Any guidance appreciated. Thanks!
3
votes
3answers
90 views

Number of Solutions of $y^2-6y+2x^2+8x=367$? [closed]

Find the number of solutions in integers to the equation $$y^2-6y+2x^2+8x=367$$ How should I go about solving this? Thanks!
2
votes
2answers
194 views

Strictly monotonically increasing sequences of natural numbers

I have several questions with regards to these sequences: What is the cardinality of the set of all such sequences? I assume that it is equal to the cardinality of $\mathbb{R}$, is that correct? ...
1
vote
1answer
77 views

Pigeon-Hole Problem

Let $p$ and $q$ be two positive integers so that the largest common divisor of $p$ and $q$ is 1. Prove that for any non-negative integers $s\leq p-1$ and $t\leq q-1$, there exists a non-negative ...
9
votes
4answers
109 views

Sum of $2$ equal squares also a square

Is there an integer solution to $a^2 + a^2 = b^2$? Because there's this universift that has this logo of the pytagorean theorem where the two squares are equal, but I don't think it's possible.
0
votes
3answers
48 views

Finding a linear combination of integers of infinite set $A$, that gives the gcd of $A$

This is a follow up to my previous question, were I asked for a proof, that for any nonnempty set of integers $A$, not all zero, the greastet common divisor of $A$ exists. If $A$ is finite, with ...
1
vote
0answers
52 views

Produce all solutions for $2a^2 + b^2 = c^2$ [duplicate]

I'm trying to generate a stream of tuples $(a, b, c)$ that satisfy the equation $2a^2 + b^2 = c^2$ The first $10$ results are: $2, 1, 3$ $4, 2, 6$ $6, 3, 9$ $4, 7, 9$ $6, 7, 11$ ...
0
votes
1answer
63 views

Prove or disprove $a^{\varphi(m)}=a^{k\,\varphi(m)}\pmod{m}$

Prove or disprove that $a^{\varphi(m)}=a^{k\,\varphi(m)}\pmod m$ where $\varphi(m)$ is the totient function, and $k\ge1$. This is clearly true when $\gcd(a,m)=1$ since both sides are $1$ due to ...
0
votes
1answer
71 views

Natural Number Generator

Motivated with this question I formulated following question : Does $\lfloor \sqrt{p} \rfloor$ generate all natural numbers where $p$ is a prime number of the form $4k+3$ ? I wrote Maxima ...
2
votes
1answer
48 views

Question regarding gcd in polynomial ring over a field

Let $\mathbb{F}_q$ be a finite field. We have a polynomial ring $\mathbb{F}_q[t]$ and its field of fractions, which we denote $\mathbb{K}$. Suppose I have polynomials $f_1, \ldots, f_n$ in ...
8
votes
4answers
158 views

Prove without induction $2^n \mid (b+\sqrt{b^2-4c})^n + (b-\sqrt{b^2-4c})^n $

Prove $2^n \mid (b+\sqrt{b^2-4c})^n + (b-\sqrt{b^2-4c})^n $ for all $n\ge 1$ and $b,c$ are integers. Is it possible to prove this without induction?
2
votes
3answers
188 views

Natural numbers in set theory is {0,1,2,…}?

The set of natural numbers $\mathbb{N}$ in set theory is defined with the axiom of infinity as the smallest inductive set and then it is usually proven that $\mathbb{N}$ satisfies the Peano axioms and ...
0
votes
2answers
56 views

Solve the system of modular equations

I have the system $$2^a \equiv 7 \mod 27 \\2^{18} \equiv 1 \mod 27$$ How can I solve this system? I was thinking of using Chinese remainder theorem but 27 and 27 are not coprime.
3
votes
1answer
80 views

show that $n + \lfloor \sqrt{n} + \frac{1}{2}\rfloor$ is never a perfect square for all positive integers $n$

show that $n + \lfloor \sqrt{n} + \frac{1}{2}\rfloor$ is never a perfect square for all positive integers $n$ I am thinking of a proof by contradiction by assuming $n + \lfloor \sqrt{n} + ...
-1
votes
1answer
30 views

Question about exercise 14 on p.14 of Nathanson's Elementary Methods in Number Theory

I am revising some elementary number theory using Nathanson's book. My answer to question $14$ on page $14$ (see image) is $u = 5u' -3v'$, $v=-3u'+2v'$. Nathanson suggests that $u=u'$, $v=v'$. Did I ...
23
votes
3answers
340 views

Is every natural number representable as $\sum\limits_{k=1}^{n} \pm k^3$?

A well known identity is: $$(n+3)^2 - (n+2)^2-(n+1)^2 + n^2 = 4$$ and using this identity we prove that the set $\displaystyle \{\pm 1^2, \pm 1^2 \pm 2^2,\pm 1^2\pm 2^2\pm 3^2, \cdots\}$ contains ...
2
votes
2answers
66 views

Does this proof work?

let $ a,b \in \mathbb{Q^c} $ and define $b> a$ prove that there exists a rational number x where $ b>x>a$ I have seen this proof done in a few ways some in textbooks others on this site form ...
1
vote
1answer
54 views

If $(a,b)=1$ and $p \mid a^{2}+b^{2}$ why can one assume that $|a| < \frac{p}{2}$

There is a part of Euler's infinite descent proof I can't seam to get; If $(a,b)=1$ and $p \mid a^2+b^2$ why can one assume that $|a| < \frac{p}{2}$ and $|b| < \frac{p}{2}$ ?
3
votes
2answers
61 views

the solution to $x^2=49+k\cdot12288$

I have computed $x^2=49+k\cdot12288$ for $k=0$ to an arbitrarily large integer and found $x$ has an integer solution only for $k=0$. Can someone proove that for $x^2=49+k\cdot12288$, $x$ has only ...
4
votes
0answers
34 views

How to get the nine cycles without trial and error?

Determine the nine cycles that occur in sequences of natural numbers where each succeeding term is the sum of the cubes of the digits of the previous number. My approach is to try one-by-one starting ...
0
votes
0answers
29 views

Ring structure of tuples mod k

Consider a vector of n integers $$A= a_1, a_2, ... a_n$$ Such that for another vector $$B= b_1,b_2... b_n$$ $$AB^T \equiv 0 \mod k$$ For an integer k. I was playing around with these structures ...
0
votes
0answers
24 views

Evaluate $\displaystyle\sum_{i=1}^nF^k_{p_i}$

Let $F_{p_n}$ denote the $p_n$-th Fibonacci Number where $p_n$ is $n$-th prime. Now define, $$\mathfrak{S}_k=\displaystyle\sum_{i=1}^nF^k_{p_i}$$ Is there any formula for $\mathfrak{S}_k$? I ...
5
votes
1answer
87 views

A combinatorial proof of Wilson's Theorem

I am looking for a combinatorial proof of Wilson's Theorem. Something along the lines of this kind of proof. $\textbf{Combinatorial proof of Fermat's Little Theorem}$ First consider a $p$ -tuple and ...
0
votes
1answer
28 views

Detail in the derivation of the Miller-Rabin test

In the derivation of the Miller-Rabin Primality (or actually, "probably composite") test, Wikipedia http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test as well as other sites (including ...
5
votes
4answers
304 views

For every positive integer $n, n^2 + 4n + 3$ is not a prime

Prove: For every positive integer $n, n^2 + 4n + 3$ is not a prime. I tried to disprove the statement, which I could not using several number examples with constructive proof. However I am not sure ...
1
vote
0answers
80 views

Prove $X\times Y$ is an equivalence relation [duplicate]

(Relation between two sets) If $X$ and $Y$ are sets, a relation between $X$ and $Y$ is a subset $R \subset X \times Y.$ For a relation $R \subset X\times Y$ and $a \in X$ and $b \in Y$ if $(x,y) \in ...
4
votes
1answer
92 views

Analytic solutions to a simple math trick

As proven here $3816547290$ is the only positive integer in which every digit is used; each digit is used only once; the first $n$ digits are divisible by $n$, for $n=1,...,10$. ...
4
votes
1answer
66 views

Liouville sequences

We have $(1+2+\cdots+n)^2=1^3+2^3+\cdots+n^3$. We call a finite sequence $a_1,\ldots,a_n$ Liouville if it satisfies \begin{equation}(a_1+\cdots+a_n)^2=a_1^3+\cdots+a_n^3.\end{equation} Liouville ...
2
votes
8answers
112 views

Prove $4^k - 1$ is divisible by $3$ for $k = 1, 2, 3, \dots$

For example: $$\begin{align} 4^{1} - 1 \mod 3 &= \\ 4 -1 \mod 3 &= \\ 3 \mod 3 &= \\3*1 \mod 3 &=0 \\ \\ 4^{2} - 1 \mod 3 &= \\ 16 -1 \mod 3 &= \\ 15 \mod 3 &= \\3*5 ...
0
votes
1answer
88 views

Solve $x^6 \equiv x \pmod{396}$

I have to solve the following equation: $x^6 \equiv x \pmod {396}$, with $x \in \mathrm{Z}/396\mathrm{Z} $. So I rewrote this equations as the following system: $$x^6 \equiv x \pmod4\\ ...
3
votes
1answer
23 views

Boundedness of $\gcd(|x-y|,|a_x-a_y|)$ in sequence

Let $a_1,a_2,\ldots$ be an infinite sequence of distinct positive integers, and let $n$ be a positive integer. Does there always exist integers $x,y$ such that $\gcd(|x-y|,|a_x-a_y|)>n$? When ...
2
votes
1answer
47 views

Proof, that every nonempty set of integers, not all zero, has a greatest common divisor

I'm searching for a proof or (better) a way to understand the proof from the book "Elementary methods in number theory", that every nonempty set of integers, not all zero, has a greatest common ...
3
votes
1answer
54 views

Integer $m$ such that $2^m\equiv\pm 1\pmod{2n+1}$

Let $n$ be a positive integer. Does there always exist a positive integer $m\leq n$ such that $2^m\equiv\pm 1\pmod{2n+1}$? It is true that $2^{\phi({2n+1})}\equiv 1\pmod{2n+1}$. If $2n+1$ is prime, ...
1
vote
3answers
139 views

Is natural numbers set $\mathbb N$ infinite set?

A set with uncountable number of elements is called an infinite set. Is that the set of all natural numbers, $\Bbb N=\text{{$1,2,3,\ldots$}}$ infinite set? As far i know $\Bbb N$ is "countably" ...
4
votes
2answers
304 views

Contradiction on prime decomposition

Take $n = 12$ $12$'s prime factorization is $2^1\times2^1\times3^1$ So then, the number of factors by UFT is $(1+1)(1+1)(1+1) = 8$ But there's only $1,2,3,4,6,12 = 6$ factors!! Where are the other ...
6
votes
1answer
57 views

Multiplicative structure without unique prime factorisation

The subset $N:=\{3n+1\colon n\in\mathbb{N}\}$ is closed under multiplication. 4, 10 and 25 are prime numbers in $N$. We have $100=4\cdot 25=10\cdot 10$, hence factorisation with prime numbers in $N$ ...
6
votes
2answers
199 views

Prove that the elements of the triangle sum have even numbers of divisors.

Consider the sum $$S = \sum_{k=1}^n k$$ As I was computing the first triangle number with over 500 divisors (Project Euler), I came across the hypothesis that most triangle numbers have an even ...
7
votes
1answer
148 views

Generating mirror numbers

(This was a question asked by my dear little 10 year old brother.) Let's define some kind of algorithm, where we take a number, reverse its digits, and add it to the original, and iterate until we ...
1
vote
1answer
57 views

Lehmer's conjecture/Lehmer's totient problem

I came across Lehmers problem in Wikipedia and do not grasp why it may be of any interest. Are there any serious consequences or insights if it is really confirmed ? I suppose people who struggle(d) ...
8
votes
1answer
58 views

Remainder when dividing by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$

Given a $54$-digit number consisting of only ones and zeros. Prove that the remainder when dividing this number by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$. The number can be written ...
2
votes
1answer
25 views

Distinct integers with $a=\text{lcm}(|a-b|,|a-c|)$ and permutations

Do there exist three pairwise different integers $a,b,c$ such that $$a=\text{lcm}(|a-b|,|a-c|), b=\text{lcm}(|b-a|,|b-c|), c=\text{lcm}(|c-a|,|c-b|)?$$ None of the integers can be $0$, because the ...
6
votes
5answers
83 views

$x^2-y^2=2s$, s cannot be an odd integer

How can we prove that if $x^2-y^2=2s$ holds, s cannot be an odd integer. What theorem in number theory should we use?
3
votes
1answer
69 views

What is an insightful proof ( not a verification ) of the Quadratic Reciprocity Law?

Helmut Koch wrote in "Introduction to classical mathematics" (Springer, 1986) about the Quadratic Reciprocity Law: "... Altogether Gauss gave seven proofs of this theorem, however they should all be ...
4
votes
2answers
144 views

Is every sufficiently large positive integer of the form $ab + ac + bc + 1$?

Is every sufficiently large positive integer $A$ of the form $ab + ac + bc + 1$ where $a,b,c$ are some positive integers larger than some given positive integer $d$ ? How large is sufficiently ...