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

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

How can I find the common solution for the following linear congruences :

How can I find the common solution for the following linear congruences : $1)$ $x \equiv 5$(mod$13$) $x \equiv 3$(mod$12$) $x \equiv 2$(mod$35$) $--------------------$ $2)$ $x \equiv ...
4
votes
1answer
32 views

Irrational Numbers : Show that $0.1248163264…$ is irrational

I was working through some basic Number Theory Problems in Rosen and came across the following problem : Show that the real number $0.1248163264...$ represented in ...
0
votes
3answers
29 views

Diophantine Equations : Solve $a^2 + b^2 = 4c + 3$

I was working my way through some number theory problems , when I came across the following question : Find all solutions to the equation $a^2 + b^2 = 4c + 3$ My Solution (partial) : If ...
6
votes
2answers
57 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 ...
-1
votes
3answers
40 views

basic word problem! [on hold]

Find the smallest number by which $108$ must be multiplied to give a multiple of $80$.
3
votes
3answers
25 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 ...
0
votes
3answers
40 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, ...
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 ...
2
votes
2answers
53 views

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $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 ...
5
votes
5answers
69 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!
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
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$ ...
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 ...
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, ...
0
votes
1answer
40 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$ ...
5
votes
0answers
71 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
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...
21
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 ...
1
vote
1answer
123 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 ...
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
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 ...
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 ...
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 ...
-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?
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 ...
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$$?
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
62 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 ...
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 ...
2
votes
1answer
52 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 ...
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$ = ...
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: ...
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. ...
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 ...
0
votes
1answer
18 views

Lowest Common Multiple of multiple pairwise coprime integers?

I've seen that the equation $$\text{gcd}(a,b,c)\times \text{lcm}(a,b,c)=abc$$ Is true provided that $a,b,c$ are pairwise coprime. However surely then this equation has no significance as ...
-4
votes
0answers
45 views

Why aren't natural numbers inherently present in the universe? [on hold]

This may seem like a strange question, as I am sure every mathematician would argue that positive integers are present in the universe. Hear me out. In order for an integer to exist, it must be in ...
3
votes
0answers
38 views

What is the densest, most opaque way of saying two odd numbers add up to an even number? [on hold]

Here's what I've come up with: In $\mathbb Z$, any pairwise sum of elements in the $\langle 2 \rangle + 1$ coset is in $\langle 2 \rangle$. But there's got to be a way to make this even briefer, ...
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$ ...
1
vote
1answer
32 views

elementary number theory proof

A student that I'm tutoring showed me the following problem: Let $a\gt 1,$ and $k,n\gt 0.$ Prove that $a^k-1\mid a^n-1$ if and only if $k\mid n$. Solution: Since $k$ divides $n$, we have ...
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 ...
5
votes
1answer
35 views

Prove that every nearly euclidean domain is a principal ideal domain.

An integral domain $R$ is called nearly euclidean if there is a function $$N:R \setminus \{0\} \to \mathbb{Z}^{>0} $$ satisfying the following property: for every $a,b \in R$ with $a \ne 0$, we ...
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 ...
2
votes
2answers
42 views

Suppose $p$ is a prime number and $a$ is an integer. Show that if $p \mid a^n$, then $p^n \mid a^n$ for any $n \geq 1$?

I know that if $p \mid a^n$, I can say $a^n = pr$ for some integer $r$, you can also conclude that $\gcd(p, a^n) = p$, but I'm not sure how to use that information if I even can to show that $p^n \mid ...
0
votes
2answers
31 views

Modular of a float number

Can you please help me how to get the result of the equation: 9.9 mod 13? It may seems an stupid question (!) but you will very help me by your answers to the question. Thank you
4
votes
0answers
40 views

$4$ different square numbers can't create an arithmetic sequence. [duplicate]

I have the following task: Prove, that four different square numbers can't create an arithmetic sequence(obviously, the $0,0,0,0$ case is forbidden). How can I prove this statement? I tried to write ...
4
votes
1answer
87 views

Sum and difference of two square numbers.

I have the following task: Prove, that the sum and the difference of two (not $0$) square numbers can't be both square numbers. For the sum, I thought about Pythagoras numbers: $x^2+y^2=z^2$ works ...