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

learn more… | top users | synonyms (1)

3
votes
1answer
40 views

Divisibility of $6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$

Prove or disprove that for all natural $n$ $$6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$$ is divisible by $259$. I tried to apply mathematical induction, but ...
2
votes
3answers
22 views

Largest subset with no arithmetic progression

I am trying to find some weak bounds on the largest subset of a set, such that the subset has the property that it contains no three elements in arithmetic progression. The elements of the original ...
-1
votes
3answers
36 views

basic word problem! [on hold]

Find the smallest number by which $108$ must be multiplied to give a multiple of $80$.
38
votes
3answers
3k views

Is $n! + 1$ often a prime?

Related to this question, I wonder how often $n!+1$ is a prime? There is a related OEIS sequence A002981, however, nothing is said if the sequence is finite or not. Does anybody know more about it?
0
votes
2answers
41 views

Find all solutions $x^{23}=5$ in $\Bbb Z_{23}$ for $x \in \Bbb Z_{23}$?

I just found that $5$ is a solution by using Fermat's theorem. But, I am not sure whether there are more solutions and how I could find them...
4
votes
1answer
44 views

Sums of reciprocals of subsets of natural numbers

There exists such a subset $A$ of the reciprocals of natural numbers $\{\frac{1}{n} \ |\ n \in \mathbb N\}$ that any real number $x$ on the interval $[0,1]$ can be expressed as sum of members of some ...
14
votes
3answers
912 views

A fun problem by Arnold using the Poincaré recurrence theorem

I came across this problem by V. I. Arnold while studying his classical mechanics book. Consider a sequence where the $n^{th}$ term is made up by considering the first digit of $2^n$, the first ...
20
votes
3answers
1k views

Is it possible for integer square roots to add up to another?

I initially was wondering if it were possible for there to be three $x,y,z \in \mathbb{Q}$ and $\sqrt{x},\sqrt{y},\sqrt{z} \notin \mathbb{Q}$ such that $\sqrt{x} + \sqrt{y} = \sqrt{z}$. I had ...
3
votes
12answers
1k views

Measure 11 liters using bottles of 16, 6, and 3 liters

This question has been bugging me for a day and finally I gave up and decided to ask the community for it so here's how it goes: Suppose we have 3 bottles with capacities of $16,6$ and $3$ liters, ...
5
votes
5answers
67 views

solutions such that a combination number is odd

Let $m$ be a positive integer. Given $m$, I want to find the largest $n$, $1\leq n\leq m$, such that $$m+n\choose n $$ is odd. Is there any standard theorems or results? Any references? Thanks!
1
vote
3answers
41 views

How to apply Chinese Remainder Theorem for $x$

If: $$x \equiv 0 \pmod{17}$$ and $$x \equiv -1 \pmod{9}$$ Then how is: $$x \equiv 17 \pmod{153}$$ I get that since $\gcd(9, 17) = 153 $ the solution will be $\pmod{153}$ but how do you get the $17 ...
0
votes
3answers
38 views

Number of times $2^k$ appears in factorial

For what $n$ does: $2^n | 19!18!...1!$? I checked how many times $2^1$ appears: It appears in, $2!, 3!, 4!... 19!$ meaning, $2^{18}$ I checked how many times $2^2 = 4$ appears: It appears in, ...
2
votes
3answers
64 views

$a^2 = 2b^3 = 3c^5$ Find the smallest value of $abc$.

We have following equation: $a^2 = 2b^3 = 3c^5$ Where $a, b, c$ are natural numbers. Find the smallest possible value of product $abc$.
1
vote
4answers
53 views

Is $\gcd(2^{2n}+1, 3)=1$?

Can any one prove that $2^{2n}+1$ and $3$ are relatively prime for any integer $n$? I tried with a Matlab program and computed this gcd upto $n= 25$. I got 1 for all of them. So I suppose that the ...
0
votes
1answer
29 views

Find the smallest $m$

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$. $m$ is a 3 digit number (because this was an AIME problem). $$m \equiv 0 \pmod{17}$$ $$m \equiv 17 ...
1
vote
3answers
62 views

What are the possible values of $a$ such that $f(x) = (x + a)(x + 1991) + 1$ has two integer roots?

What are the possible values of $a$ such that $f(x) = (x + a)(x + 1991) + 1$ has two integer roots? $(x + a)(x + 1991) + 1 = x^2 + (1991 + a)x + (1991a + 1)$ This is of the form $ax^2 + bx + c$. ...
1
vote
1answer
23 views

Number of $q$-th residues modulo $n$

Let $q$ be a prime and $n\ge 2$ an integer. Moreover, define $f_q(n)$ as the number of $q$-th residues modulo $n$. Is it true that if $K$ is a positive constant then there exist infinitely many $n$ ...
5
votes
0answers
68 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
0
votes
0answers
36 views

Construction of Natural Numbers

I am trying to prove that the natural numbers can be constructed from the product of a power of $2$ and an odd number. For all $n \neq 0$ in the natural numbers, $n = (2k+1)(2^p)$, where $k$ and $p$ ...
4
votes
4answers
113 views

Show that there does not exist an integer $n\in\mathbb{N}$ s.t $\phi(n)=\frac{n}{6}$

Show that there does not exist an integer $n\in\mathbb{N}$ s.t $$\phi(n)=\frac{n}{6}$$. My solution: Using the Euler's product formula: $$\phi(n)=n\prod_{p|n}\Bigl(\frac{p-1}{p}\Bigr)$$ We have: ...
2
votes
2answers
59 views

If sum of seven distinct natural numbers is 100 How to prove that there exist at least one group of three numbers whose sum is 50

There are $7$ distinct natural numbers whose sum is $100$. From these 7 numbers 3 numbers can be selected in $C(7,3)=210$ ways How to prove that at least one of these groups will have sum at least ...
1
vote
0answers
24 views

The exponent on Thue's theorem

I have been reading about Runge's theorem on diophantine approximation Theorem. Let $\xi$ be an algebraic real number of degree $d\geq 3$. For every $\epsilon >0$ there is a number $\gamma >0$ ...
4
votes
2answers
106 views

How do I prove that $ f(n) = (n + 1)! - 1 $ is an injective function?

I have this problem: Consider the function $f : \mathbb{N} \rightarrow \mathbb{N}$ defined, for every $n \in \mathbb{N}$, by $$f(n) = (n+1)! - 1$$ Prove that $f$ is injective. How do I ...
0
votes
1answer
24 views

Contraharmonic mean given harmonic mean

Given that two positive integers, $X$ and $Y$, have a harmonic mean of $6.875$, what is their contraharmonic mean. Harmonic mean is $(2XY)/(X+Y)$ and contraharmonic mean is $(X^2 +Y^2)/(X+Y)$. I began ...
11
votes
1answer
237 views

Is the equation $\phi(\pi(\phi^\pi)) = 1$ true? And if so, how?

$\phi(\pi(\phi^\pi)) = 1$ I saw it on an expired flier for a lecture at the university. I don't know what $\phi$ is, so I tried asking Wolfram Alpha to solve $x \pi x^\pi = 1$ and it gave me a bunch ...
2
votes
1answer
50 views

Using Fermats prime numbers to prove that there is infinitely many prime numbers

A Fermat number $F_n$ is of the form $F_n = 2^{2^n} + 1$ Furthermore, $F_n = 2 + F_0F_1F_2......F_{n-1}$ Now I already proved that if $n \neq m$ then $\gcd(F_n,F_m) = 1$ Here is the proof Without ...
6
votes
3answers
196 views

I finally understand simple congruences. Now how to solve a quadratic congruence?

Now that I have plain old congruences, $19x\equiv 4 \pmod {141}$ for example, I am trying to wrap my brain around quadratic ones. My textbook shows how to tackle the aforementioned congruences, but ...
8
votes
1answer
151 views
+100

Equality by iteratively applying $(a,b)\rightarrow [(a+1,2b)\text{ or }(2a,b+1)]$?

I play a game starting with $2$ positive integers $a$ and $b$. At each step of the game I can double one of the integers and add $1$ to the other integer. Is there always a procedure for any ...
1
vote
1answer
122 views

Isn't really a monotonic sequence?

First, I'd to say that I'm a beginner so may you answer easily plz. I'll expose you the problem: I was looking up on this page http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF and find ...
0
votes
0answers
41 views

Prove that if $(n-1)!\equiv-1 \mod n$ then $n$ is prime. [duplicate]

Let n be a natural number, $n\ge 2$. Prove that if $(n-1)!\equiv-1 \mod n$ then $n$ is prime. I tried few things but I my skills in equations modulo $n$ are not well enough. I would really appreciate ...
0
votes
2answers
18 views

Sum of polynomial coefficient

Steve says to Jon, "I am thinking of a polynomial whose roots are all positive integers. The polynomial has the form $P(x)=2x^3-2ax^2+(a^2-81)x-c$ for some positive integers $a$ and $c$. Can you ...
1
vote
3answers
37 views

Given $n \in \Bbb Z$, determine $\gcd(3n^2 + 7n + 4, n + 2)$.

I factored $3n^2+7n+4$ to $(3n+4)(n+1)$ and because there isn't a common factor of those and $n+2$ I said that the gcd is $1$, but is there any othere way to go about it that would come up with a gcd ...
2
votes
2answers
35 views

How many distinct numbers can I get mod 8

so I have the following $(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)$ I want to see how many distinct numbers can I get mod $8$ by adding from this list 3 times for example I got so ...
6
votes
2answers
75 views

Pythagorean Triples : Is every positive integer $\gt$ $2$ part of at least one Pythagorean triple?

I was doing some basic number theory problems from Rosen and came across this problem: Show that every positive integer $\gt$ $2$ is part of at least one ...
5
votes
1answer
67 views

An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
15
votes
2answers
94 views

For $N\in \mathbb{N}$, do there exist natural numbers $N<n_1<n_2<\cdots<n_k$ such that $\frac{1}{n_1}+\cdots+\frac{1}{n_k}=1$?

$N$ is a natural number. Is there any $k$ and some natural numbers $N<n_1<n_2<\cdots<n_k$ such that $$\frac{1}{n_1}+\frac{1}{n_2}+\cdots+\frac{1}{n_k}=1$$?
1
vote
1answer
29 views

Prove that 2 is irreducible in $\mathbb{Z}[\sqrt{n}]$ if n has a prime factor congruent to 5 modulo 8.

Prove that $2$ is irreducible in $\mathbb{Z}[\sqrt{n}]$ if $n$ has a prime factor congruent to 5 modulo 8. I know that if $x^2 \equiv \pm2\pmod p$, where $p$ is a prime, has no solution if $p ...
2
votes
3answers
46 views

Integral intersections between quadratic sequences

How can I find the integer solutions to: $$ x^2=\frac{1}{2} n (n+1) $$ By brute force I have found the solutions (6,8) (35,49) and (204,288) but then it gets harder. Note that the perfect squares ...
-1
votes
4answers
49 views

Find the last digit of $\binom{2016}{21}$

Find the last digit of the binomial coefficient: $$\binom{2016}{21}$$ I would start by factorial form: $$\binom{2016}{21} = \frac{2016!}{21!(1995!)}$$ But that doesnt help much?
6
votes
4answers
79 views

Prove that if $p$ is a prime such that $p^2+2$ is a prime then $p=3$.

My problem in my solution is that I don't know if the operations I apply on congruence modulo n are admissible. I could really use some guiding: Attempt: Let there be $p\ne 3$ fulfilling the ...
4
votes
3answers
61 views

Prove that ${x^2+y^2=z^n}$ has a solution in $\mathbb{N}$ for all $n$ in $\mathbb{N}$

I am solving it by stating that $$x^2 +y^2 =c^2$$ represents a circle. And when $$c^2=z^n$$ then , it represents a system of concentric circles with radius varying as $z$ varies or $n$ varies. So, for ...
1
vote
0answers
27 views

$\sum_{n=i}^{j}\frac{1}{n}$ Isn't Integer Without Bertrand's Postulate [duplicate]

$i,j\in \mathbb{N}$ and $i<j $. Prove that $$\sum_{n=i}^{j}\frac{1}{n}$$ isn't integer using without using the Bertrand's postulate.
1
vote
1answer
15 views

Invariance Principle Question

A circle is divided into six sectors. Then the numbers $1, 0, 1, 0, 0, 0$ are written into the sectors (counter-clockwise say). You may increase two neighboring numbers by $1$. Is it possible to ...
1
vote
2answers
19 views

Proving expressibility of integers as the difference of two squares.

I'm given the task: Prove that a positive integer is expressible as the difference of two squares of integers if and only if it is not of the form $4n+2, n\in\mathbb{Z}$ I was given a hint that I ...
2
votes
0answers
19 views

Argument verification fermat divisors.

any prime divisor of p is of the form then p = k $2^{n + 1}$ + 1 for n $\geq$ 2. We can use the result that Any divisor of $F_n$ is of the form q = k * $2^{n + 1}$ + 1 (*) Given that $F_n$ = ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...
0
votes
1answer
18 views

Proof involving primitive Pythagorean triples

Currently learning about primitive Pythagorean triples and I'm having trouble approaching the following proof. Given that $x, y, z$, is a primitive Pythagorean triple with $y$ even, I need to show: ...
15
votes
6answers
1k views

Prove $a+b+c+d $ is composite

Let $a,b,c,d$ be natural numbers with $ab=cd$. Prove that $a+b+c+d$ is composite. I have my own solution for this (As posted) and i want to see if there is any other good proofs.
3
votes
4answers
126 views

Proof that the product of primitive Pythagorean hypotenuses is also a primitive Pythagorean hypotenuse

Just to be clear, I call an integer $c$ a 'primitive Pythagorean hypotenuse' if there exist coprime integers $a$ and $b$ satisfying $a^2+b^2 = c^2$. I noticed that the set of such primitive ...