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

learn more… | top users | synonyms

0
votes
0answers
8 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
18 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 ...
2
votes
1answer
56 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
18 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
5answers
181 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 ...
0
votes
0answers
51 views

Prove $X\times Y$ is an equivalence relation

(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 ...
-5
votes
1answer
43 views

elementary number theory (greater integer function ) problem? [on hold]

5(b): For what values of n does n! terminates in 37 zeros ? This is from here.
4
votes
1answer
70 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
57 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
6answers
49 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
0answers
42 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
18 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
27 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
50 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, ...
4
votes
2answers
284 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
46 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
147 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 ...
6
votes
1answer
37 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
33 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
51 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 ...
4
votes
1answer
71 views

What motiveted Gauss to formulate his theorem on quadratic reprocity?

Im trying to connect his work on quadratic reciprocity with some simple question, like solution to certain diophantine equation or representing primes. Any ideas? I find it hard to imagine that he out ...
2
votes
0answers
14 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 ...
5
votes
5answers
69 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
54 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
133 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 ...
2
votes
2answers
50 views

If $\gcd(a,n)=1$ then there exist integers $x,y$ such that $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y \pmod n$

If $a$ is integer and $n$ is positive integer such that $\gcd(a,n)=1$ then there exist integers $x,y$ for which $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y\pmod n$. By Dirichlet's principle I ...
2
votes
3answers
42 views

Is $ x^n-y^n$ is a product of coprime factors?

In the expression: $x^n-y^n$, if $n>2$ and $x,y$ are relatively prime, are the factors $x-y$ and $ x^{n-1}+x^{n-2}y+.....$ always coprime? Why? Please exclude the cases where $x-y=\pm 1$ and $\pm ...
0
votes
0answers
15 views

What is the “cost” of computation of two special CAS algorithms

Suppose I have an integer $n$ with e.g. a large number of say decimal digits. I would like to get some information about the runtime "cost" of standard CAS algorithm which factors $n$ into primes ...
4
votes
0answers
47 views

Extention of Euclid's GCD Algorithm. (The Art of Computer Programming, Volume 1, Edition 3, Section 1.2.1, Exercise 12)

Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$, needs the inputs to be positive integers. Exercise 12 provides an extension to this algorithm and allows $c$ ...
-5
votes
1answer
55 views

A big challenge on Number theory [on hold]

Let $N=\frac{60^{2014}}{7}$. What is the sum of the first $2014$ digit before the decimal point of $N$?
1
vote
0answers
24 views

Determining the starting value for primality test

This question is about Lucasian primality test for numbers of the form $N=3\cdot 2^n-1$ . There is a following statement in Wikipedia article : Lucas-Lehmer-Riesel test : "If $k = 3$ : if $n = 0$ ...
3
votes
1answer
37 views

Diophantine equation involving factorial …

Question . Find all positive integer solutions to the equation below , $$(n-1)!+1=n^m$$ (i)observe that $n>1$ and $n$ is a prime number (if not we can choose a prime number $p<n$ such that $p|n$ ...
6
votes
0answers
64 views

When can $n^k+k$ be a perfect square?

For what positive integers $k$ does there exist a positive integer $n$ such that $n^k+k$ is a perfect square? Certainly for all $k$ such that $k+1$ is a perfect square, since we can substitute $n=1$. ...
3
votes
1answer
42 views

What is the discrete log used for?

Perusing Wikipedia, I stumbled on the discrete logarithm. I looks interesting that we'd be able have a function that could solve $b^k=g$ for integers $b,k,$ and $g$. However, Wikipedia says "No ...
5
votes
1answer
67 views

Is this an accurate proof that no perfect square is of the form $4k+3$? ($k$ an integer)

A positive integer $n$ is a perfect square. Prove that it cannot be of the form $4k+3$, where $k$ is an integer. I tried to prove this by proof by contradiction: if $n$ is a perfect square, then ...
1
vote
1answer
24 views

Congruence with $x$ in a power

I don't know how to find $x$ in a situation like this: $$a^x \equiv b \pmod c$$ I think I'm missing something around little fermat theorem, Could anyone help?
-1
votes
1answer
40 views

Relations between the GCD of two numbers and the GCD of their linear combinations

(a) Prove that $a|b$ if and only if $\gcd(a,b) = a$. (b) Let $b > 9a$, Show that $\gcd(a,b) = \gcd(a,b−2a)$ (c) Show that If $a$ is even and $b$ is odd, then $\gcd(a,b) = \gcd(a/2,b)$ (d) Show ...
1
vote
2answers
45 views

How prove this diophantine equation $x^2-y^2\equiv a\pmod p$ have only $p-1$roots

Question: let $a\neq 0$.and $p$ is prime numbers. show that the number of ordered two-tuples $(x,y)$such this following diophantine equation $$x^2-y^2\equiv a\pmod p$$ at most $p-1$ ...
8
votes
0answers
36 views

Divisors of sequence $n,P(n),P(P(n)),\ldots$

Let $P(x)$ be a polynomial with nonnegative integer coefficients consisting of more than one nonzero term. Let $n$ be a positive integer. Is the set of prime numbers which divide at least one number ...
8
votes
1answer
54 views

Congruence properties of $a^5+b^5+c^5+d^5+e^5=0$?

It is known that given a solution to, $$a^4+b^4+c^4 = d^4\tag1$$ then either $-c+d,\;c+d$ is always divisible by $2^{10}$. For example, $$95800^4+414560^4+217519^4=422481^4$$ then ...
3
votes
3answers
74 views

Writing number as sum of reciprocals of factorial

Given a real number $r>0$. Is there a way to determine whether $r$ can be written as a (possibly infinite) sum of distinct terms of the form $1/n!$? For example, if we want to determine whether ...
2
votes
2answers
137 views

Proof by Contradiction on prime numbers [duplicate]

Prove using contradiction that any prime number greater than $3$ is of the form $6n \pm 1$. Thanks for any help
0
votes
1answer
12 views

Rational roots of a polynomial with integral coefficients and constant term 1.

Here is the problem I am working on from Hardy "A course of Pure Mathematics." Given the polynomial with integral coefficients $x^n+p_1x^{n-1}+p_2x^{n-2} + \cdots + p_n = 0$, with $p_n=1$, and ...
2
votes
0answers
57 views

Is there a solution to $a^4+(a+d)^4+(a+2d)^4+(a+3d)^4+\dots = z^4$?

One can be familiar with, $$31^3+33^3+35^3+37^3+39^3+41^3 = 66^3\tag{1}$$ I found, $$29^4+31^4+33^4+35^4+\dots+155^4 = 96104^2\tag2$$ which has $m=64$ addends. The equation, ...
0
votes
1answer
46 views

Find all positive integers $a,b,c,d$ with given conditions. [on hold]

Find all positive integers $a, b, c, d$ such that $$\left(1+\frac{1}{a}\right)\left(1+\frac{1}{b}\right)\left(1+\frac{1}{c}\right)\left(1+\frac{1}{d}\right)-\frac{1}{abcd}$$ is a positive integer. ...
1
vote
2answers
63 views

About the infinitude of some kind of primes? [on hold]

I will propose this proof: A Mersenne number always has the form $$2^{p}-1=4n+3$$ since for all $p≥2$ we have $$2^{p}-1≡-1(mod4)≡3(mod4)$$ The Dirichlet prime number theorem ...
2
votes
1answer
38 views

Prove that if $\{a_n\}$ is a sequence of natural numbers such that $\{ a_n^{-1}\}$ is an arithmetic sequence then all $a_i$ are equal

Prove that if $\{a_n\}$ is a sequence of natural numbers such that $\left\{\frac{1}{a_n}\right\}$ is an arithmetic sequence then all the $a_n$s are equal. I have no clue where to begin from, ...
4
votes
1answer
27 views

Sequences that misses exactly the Polygonal and the $n$-th power numbers

Can you give an example any such sequence $u_n$ such that it misses exactly the Polygonal Numbers, say for example misses exactly the Pentagonal Numbers and so on? Can you give an example any such ...
1
vote
1answer
18 views

Are Primitive Dirichlet Characters linearly independent.

For a positive integer $N$, let $$S_N=\{ \chi~\mid~ \chi \text{ is primitive Dirichlet characters modulo }F,\text{ where } F\mid N \}.$$ I want to check the Linear independence on $S_N$. More ...
0
votes
3answers
66 views

How do I prove that $x^2 ≡ 3 \mod4$ has no solutions? [closed]

The congruence $x^2 ≡ 3 \mod4$ has no solutions. How do we prove that it has no solutions?