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

learn more… | top users | synonyms (1)

5
votes
1answer
52 views

Prove that $(ab,cd)=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$

I'm working through Oystein Ore's Number Theory and its History. On p. 109, I'm stuck on #2. The question asks the reader to verify the following identity [Note: $(x,y)=\gcd(x,y)$]: ...
3
votes
3answers
67 views

A puzzle about numbers which do not have 2 in their decimal representation

I came across this puzzle recently which I hope people might enjoy. Let $S(n)$ be the set of positive integers less than $n$ which do not have a $2$ in their decimal representation and let ...
3
votes
1answer
38 views

An interesting fact about the number 123456789 and its generalization in arbitrary base

The number $(12\ldots(b-1))$ in base $b$ has the property that when multiplied by any integer $1\le k\le b-1$ which is coprime to $b-1$, its digits are permuted. Why? For example in base 10, ...
-4
votes
2answers
44 views

Making a Perfect square [closed]

How to get max value of $-2x^2+3x+5$ by making perfect square. I got wrong ans. Correct ans. Must be $49/8$.
0
votes
0answers
29 views

For a given $n$, under what condition(s) there exists (at least) two different $c$ and $c'$ such that $X_n^c=X_n^{c'} $?

Let $X_n^c=\{\cos\left((4k-c)\frac{\pi}{2n}+\frac{\pi}{4}\right): k=0, 1, \dots, n-1\}$ where $c\in\{0, 1, \ldots, \lfloor\frac{n}{2}\rfloor\}$ and $n$ is any positive integer greater than 3. I want ...
9
votes
1answer
87 views

Prove that neither $A$ nor $B$ is divisible by $5$

Let the sum $\mathbf {1+ \frac12 + \frac13 + \frac 14+ \dots +\frac1{99} + \frac 1{100}}$ be written as $\frac AB$, where $A$ and $B$ are positive integers with no common factors. Show that neither ...
5
votes
1answer
170 views

Conjectured compositeness tests for $N=k \cdot 2^n \pm c$

How to prove that these conjectures are true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ...
1
vote
1answer
42 views

If $\varphi(mn)=\lambda \varphi(m)\varphi(n)$ what should be written for $\lambda$

Respected All. I am studying number theory where I came to know that $\varphi(n), \sigma(n)$ both are multiplicative function ; In other words, if $(m,n)=1$ then \begin{align} ...
1
vote
3answers
39 views

What is the smallest possible natural number $𝑛$ for which $x^{2}-nx+2014=0$ has integer roots?

What is the smallest possible natural number $𝑛$ for which the equation $x^{2}-nx+2014=0$ has integer roots? My idea was, If the roots are integers, then they are the divisors of $2014$, I don't ...
3
votes
0answers
48 views

Debunking an elementary proof of FLT

José Cayolla: Fermat's Last Theorem admits an infinity of proving ways and two corollaries. arXiv:1507.06989 [math.GM] I don't usually devote so much time to "crackpot papers", but I have a ...
7
votes
1answer
75 views

Find the least positive integer $n$ so that $\left ( 1-\frac{1}{s_{1}} \right ) \cdots \left ( 1-\frac{1}{s_{n}} \right )=\frac{51}{2010}$

Find the least positive integer $n$ for which there exists a set $\left \{ s_{1}, s_{2},....,s_{n} \right \}$ consisting of $n$ distinct positive integers such that $$\left ( 1-\frac{1}{s_{1}} ...
1
vote
2answers
36 views

Proving that $\text{gcd}(a,b)=\text{gcd}(b,r)$

Let $0\neq a,b\in \mathbb{Z}$. there are integers $p,q$ such that $0\leq r<b$ and $a=bq+r$. Prove that $(a,b)=(b,r)$ My attempt: $$\text{gcd}(a,b)=\varphi$$ So $$\exists \,m,n \in ...
0
votes
1answer
19 views

Find the maximum sum of real part roots

Let $z_1,z_2,z_3,\dots,z_{12}$ be the 12 zeroes of the polynomial $z^{12}-2^{36}$. For each $j$, let $w_j$ be one of $z_j$ or $i z_j$. Then the maximum possible value of the real part of ...
-2
votes
1answer
23 views

How does this proof on quadratic congruences make sense?

Could I get some help with this proof? It is supposed to be induction, but I have no idea where the $m \tilde {x_0} \frac 12 (p+1)p^k$ term near the bottom comes from. I understand how it is used for ...
0
votes
0answers
20 views

Trigonometric functions on set of co-primes to $n$

E.g. I plotted the function values of $y=\tan(x\frac{\pi}{n})$ for integer $x$-values in the range of $0,\cdots,n$ where $n$ is a given odd integer ( to prevent the case of undefined ...
-5
votes
2answers
36 views

number theory quest. [closed]

A positive integer "$n$" is called a magic number if it has the following property: if $a$ and $b$ are two positive numbers that are not coprime to $n$ then $a+b$ is also not coprime to $n$. For ...
-2
votes
1answer
31 views

Every positive even integer can be written in the form $4q$ or the form $4q+2$ [duplicate]

Show that any positive even integer is of the form 4q or 4q+2 where q is a whole number. I am trying to use division algorithm or something to show this. I want to know how Euclid's lemma can be ...
4
votes
3answers
100 views

Prove $\log_7 n$ is either an integer or irrational

I have been trying to prove a certain claim and have hit a wall. Here is the claim... Claim: If $n$ is a positive integer then $\log_{7}n$ is an integer or it is irrational Proof ...
-1
votes
2answers
32 views

How many ways to arrange colors (constraints)

Ed has five identical green marbles and a large supply of identical red marbles. He arranges the green marbles and some of the red marbles in a row and finds that the number of marbles whose right ...
2
votes
4answers
67 views

Number of Interesting Quadruples

Define an ordered quadruple of integers $(a, b, c, d)$ as interesting if $1 \le a<b<c<d \le 10$, and a+d>b+c. How many interesting ordered quadruples are there? This is a bit of trouble ...
2
votes
1answer
63 views

strange fibonacci recurrence

As it is well known fibonacci numbers satisfy the recurrence relation $$F_{n}=F_{n-1}+F_{n-2}$$ with initial conditions $F_{0}=0$ and $F_{1}=1$. While playing around with numbers,I noticed the ...
0
votes
0answers
40 views

What is Lebesgue measure of sets of inverse prime numbers in $[0,1] $?

I would like to know if it is possible to know the lebesgue mesure of sets of inverse prime numbers in $[0,1]$ Note : I think should to know in the first if the sets of primes are infinit countable ...
2
votes
1answer
50 views

Prove that $4$ divides $n$ [duplicate]

Let $a_1$,$a_2$,$a_3$,.......,$a_n$ be $n$ such that each $a_i$ either $1$ or $-1$.If $a_1 a_2 a_3 a_4+a_2 a_3 a_4 a_5+......+a_n a_1 a_2 a_3=0$, then prove that $4$ divides $n$. I tried this for ...
1
vote
2answers
83 views

Is $2^n-1$ always a prime for odd values of $n$? [duplicate]

Is $2^n-1$ always a prime for odd values of $n$? $n\not=1$ Taking some odd values of $n$, I observed outcome is coming as a prime number. How to verify it? Or at-least, is $2^n-1$ always coprime to ...
0
votes
1answer
38 views

if $n > 1$ is an integer not of the form $6k + 3$, prove that $n^2 + 2^n$ is composite.

My proof. By Division Algorithm, n is one of form $6 k, 6 k+1, 6 k+2, 6 k+4, 6 k+5$. So first, If $n=6 k$, $n^2+2^n=36 k^2+2^{6 k}$. then $2$ divide it. and, divisor is not one. so, it is composite. ...
2
votes
2answers
40 views

Show that 7 is a primitive root modulo 601

How do you show that 7 is a primitive root modulo 601 without having to do many, many congruences? I'm sure there is an easier way and I should like very much to learn it.
2
votes
2answers
35 views

Prove that either the average of the numbers $a_{1}, a_{2},…, a_{n}$

Let $a_{1}, a_{2},..., a_{2n}$ be positive real numbers such that $a_{j}a_{n+j}=1$ for the values $j=1,2,...,n$ ($a$) Prove that either the average of the numbers $a_{1}, a_{2},..., a_{n}$ is ...
3
votes
1answer
33 views

Prove for primes p $>2$ that $\sum_{k=1}^{p−1}{k^{2p−1}}\equiv\frac{1}{2}p(p+1)\pmod {p^2}$

Let $p$ be an odd prime. Prove that: $$\sum_{k=1}^{p−1}{k^{2p−1}}\equiv\dfrac{p(p + 1)}{2}\pmod {p^2}$$ The problem is taken from the 2004 Canada National Olympiad. I am only able to show ...
115
votes
20answers
9k views

Mental Calculations

This is the famous picture "Mental Arithmetic. In the Public School of S. Rachinsky." by the Russian artist Nikolay Bogdanov-Belsky. The problem presented on a blackboard requires computing the ...
0
votes
1answer
79 views

Least prime number proof [closed]

Prove that 2 is the only even prime number. I know that 2 is the only even prime number. I am curious to prove it
-1
votes
2answers
39 views

Last digit of a perfect square must be $0, 1, 4, 5, 6,$ or $9$ [closed]

We know that a perfect square number can contain 0,1,4,5,6 and 9 in its unit place. How can I prove that a perfect square number cannot contain 2,3,7 and 8 in its unit place?
1
vote
1answer
41 views

Is my proof for this fact correct?

The thing ought to be proven Let $a$ and $b$ be nonzero integers that are relatively prime, and let $c$ be an integer. Show that $ax+by=c$ has an integer solution. My postulated proof that ought ...
0
votes
3answers
41 views

Prove n is a product of a square and a cube

Suppose $n\ge 2$ is an integer with the property that whenever a prime $p$ divides $n$, $p^2$ also divides $n$ (i.e., all primes in the prime factorization of $n$ appear at least to the power ...
3
votes
3answers
66 views

Let $(a, b, c)$ be a Pythagorean triple. Prove that $\left(\dfrac{􀀀c}{a}+\dfrac{􀀀c}{b}\right)^2$ is greater than 8 and never an integer.

Let $(a, b, c)$ be a Pythagorean triple, i.e. a triplet of positive integers with $a^2 + b^2 = c^2$. a) Prove that $$\left(\dfrac{􀀀c}{a}+\dfrac{􀀀c}{b}\right)^2 > 8$$ b) Prove that ...
0
votes
2answers
49 views

Distinguishable Objects in a Circular Arrangement

I asked a question, AOPS Math Jam If you look at #9: **Please CTRL:F -> ** this: *"Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least ...
0
votes
1answer
52 views

Expression of theorem by $p\Rightarrow q$ [closed]

$\sqrt 2$ is irrational. Is it true that i express this theorem in this way?: If $\sqrt 2$ is a real number, then it is irrational. Is there any better way to express this theorem by $p\Rightarrow q$? ...
4
votes
3answers
53 views

What is the minimum number of moves to change $a$ into $b$ by doubling and halving?

We are given integers $a$ and $b$, and wish to change $a$ to $b$ using these operations: (1) Map $a \mapsto \lfloor \frac{a}{2} \rfloor$. (If $a$ is even, replace it with $\frac{a}{2}$. If $a$ is ...
4
votes
2answers
49 views

Find all $n \in \mathbb{Z}_{>0}$ such that $n^2+a \mid n^3+a$

Could anyone advise me how to find all $n \in \mathbb{Z}_{>0}$ such that $n^2+a $ divides $ n^3+a,$ where $a \in \mathbb{Z} \setminus \{0\}$ is fixed ? I have checked it is necessary that $n^2+a $ ...
2
votes
1answer
30 views

The diophantine problem for $R[T]$ is solvable iff the diophantine problem for $R$ is solvable

One part of the paper that I am reading is the following: Let $R$ be a commutative ring with unity and let $R'$ be a subring of $R$. We say that the diophantine problem for $R$ with coefficients ...
3
votes
0answers
53 views

Equal partial sums of $k$ numbers of $1$ to $k$

There are two sequences of $k$ numbers, denoted as $a_{i}$ and $b_{i}$, $i\in [1,k]$. Each number is between $1$ and $k$, namely $a_{i}\in [1,k]$, $b_{i}\in [1,k]$, $\forall i\in [1,k]$. Prove that ...
2
votes
1answer
18 views

Necessary condition for a finite cyclic sum of length $4$ made of $1$ and $-1$ to be $0$

This is something I observed when I was reading the classic Problem-Solving Strategies by Arthur Engel. I liked the way he solved the following problem: Let $a_1,\ldots,a_n\in\{-1,1\}$ such that ...
0
votes
1answer
46 views

Find the smallest positive integers $a, b$ such that…

Find the smallest positive integers $a, b$ such that: i) $|a - b| = 3$ ii) the sum of digits of each of $a, b$ is divisible by $11$
2
votes
2answers
84 views

Solution to equation $4n+1 = (2k+1)^2-(2u)^2$ over the natural numbers(!)

Let $n \in \mathbb{N}$ be given, then I want to know if there are $k ,u \in \mathbb{N}$ (with $k \neq n, u \neq n$) such that $4n+1 = (2k+1)^2-(2u)^2$ holds. What makes it difficult for me is the ...
0
votes
2answers
36 views

If $p_i$ is prime then $p_i \Bbb Z \cap p_j \Bbb Z= \emptyset \ \forall i,j \in \Bbb N, i\neq j$.

If $p_i$ is prime then $p_i \Bbb Z \cap p_j \Bbb Z= \emptyset \ \forall i,j \in \Bbb N, i\neq j$. Where $a \Bbb Z=\{x\in \Bbb Z: x=0 \mod a\}$. I ran into some problem where having this lemma proved ...
1
vote
0answers
25 views

Mersenne semiprimes with square indices

A Mersenne semiprime is a semiprime of the form $2^n-1$, it can be shown that $2^n-1$ can be a semiprime if and only if $n$ is either a prime or a square of a prime. There are plenty Mersenne ...
1
vote
1answer
36 views

Solve the system of congruences (CRT)

$$560x \equiv 1 \pmod{3, 11, 13}$$ I found a few (by trial and error) $560x \equiv 1 \pmod{13} \implies x = 1 + 13k$. $560x \equiv 1 \pmod{3} \implies x = 2 + 3k$. $560x \equiv 1 ...
3
votes
3answers
60 views

Solve the following simple congruence

$$560x \equiv 1 \pmod{429}$$ I am close, I used Euclid's algorithm but the remainder is hard to go backwards. $$560 = 1(429) + 131 $$ $$429 = 3(131) + 36$$ $$131 = 3(36) + 23$$ $$36 = ...
3
votes
4answers
241 views

Integer solutions using PIE

Find the number of integer solutions to $a+b+c+d=18$ with $ 0≤a,b,c,d≤6$. With no restrictions there are: $$\binom{21}{3} = 1330$$ Ones that are invalid are: $a, b, c, d \ge 7$. But how do I ...
0
votes
1answer
47 views

Find the number of polynomials satisfying the root conditions

Let $S$ be the set of all polynomials of the form $z^3+az^2+bz+c$, where $a$, $b$, and $c$ are integers. Find the number of polynomials in $S$ such that each of its roots $z$ satisfies either ...
7
votes
2answers
111 views

First-order definition of nonnegative in integers

Given the structure $(\mathbb Z,+,-,\times,0,1)$, what's the easiest way to write "$x\ge0$" in that structure? I know that this works: $$\exists a\exists b\exists c\exists d,a^2+b^2+c^2+d^2=x$$ ...