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

learn more… | top users | synonyms

2
votes
2answers
45 views

How do I prove that if gcd(n,m) divides a-b, then $x\equiv a \pmod n$ and $x\equiv b \pmod m $ has a solution?

Let $n,m$ be positive integers $>1$. Assume that $\gcd(n,m)\mid (a-b)$ Then how do I show that $x\equiv a \pmod n$ and $x\equiv b \pmod m$ has a solution? I"m struggling with this for an hour ...
-2
votes
1answer
50 views

Find minimum possible area of brush

A rectangular brush has been moved right and down on the painting. Consider the painting as a $n × m$ rectangular grid. At the beginning an $x × y$ rectangular brush is placed somewhere in the frame, ...
0
votes
1answer
57 views

$a^k \mid a^\ell \Leftrightarrow k\leq \ell$?

What would be the formal argument for showing the following statements: Let $a\geq 2$ be an integer, then: $(i)$ $a^k \mid a^\ell$ if and only if $k\leq \ell$. $(ii)$ if $a^k | a^\ell m$ and $a\not ...
0
votes
3answers
67 views

Find the minimum of the value such $15625|(1024x-8404)$

Find the minimum of the value $x\in N^{+}$ such that $$15625\mid(1024x-8404)$$ I have found that when $x\le 50$, the condition is not satisfied. How can I find this $x$ by hand?
0
votes
1answer
17 views

On injectivity of a special function

Consider map $f$: $$ f:(1,+\infty)^2\longrightarrow P(\mathbb{N}^2)\\ f(x,y):=\{\ (n,m)\in \mathbb{N}^2\quad |\ x^n < y^m \ \} $$ The question is that whether $f$ is injective or not.It must be ...
1
vote
2answers
39 views

Prove that $[a]$ and $[n]$ are not relatively prime if and only if there is a nonzero element $[b] \in \Bbb{Z}_n$ such that $[a][b] = 0$

Here is my attempt (1) ---> First of all I know that $[n] = [0]$ and then we assume that a and n are not relatively prime then there exists an integer $x = \gcd(a,n)$ and $x \neq 1$ and so there ...
0
votes
0answers
44 views

Products of All Primes Up To The $n$th Prime

The first prime is 2. The second prime is 3. 3·2=6. The product of the first three primes is 30. The product of all the primes up to the fourth prime is 210. My question is this: Is this sequence ...
1
vote
2answers
100 views

Prove that there exist two integers such that i - j is divisible by n.

Here's the full question: Prove that, for any $n + 1$ integers, $\{x_0, x_1, x_2, . . . , x_n\}$, there exist two integers $x_i$ and $x_j$ with $i \neq j$ such that $x_i − x_j$ is divisible by $n$. ...
0
votes
1answer
51 views

Can we not apply the Hensel Lifting Lemma in this case?

Check if the equation $x^2=-1 \text{ in } \mathbb{Z}_2$ has a solution, and if it has, calculate the three first positions of the solution. So, we are looking for a solution $\pmod 2$, one solution ...
0
votes
1answer
80 views

Distance between powers of 2 and 3

As we know $3^1-2^1 = 1$ and of course $3^2-2^3 = 1$. The question is that whether set $$ \{\ (m,n)\in \mathbb{N}\quad |\quad |3^m-2^n| = 1 \} $$ is finite or infinite.
5
votes
5answers
315 views

polynomial with positive integer coefficients divisible by 24?

I have to show that $n^4+ 6n^3 + 11n^2+6n$ is divisible by 24 for every natural number, n, so I decided to show that this polynomial is divisible by 8 and 3, but I'm having trouble showing that it is ...
1
vote
3answers
60 views

find natural numbers $a$ and $b$ with a special property

Find all natural numbers $a$ and $b$ such that $\gcd(a,b)=1$ and $$\dfrac{a}{b}=b.a$$ Also $b.a$ is a decimal number. For example $\dfrac{5}{2}=2.5$
1
vote
3answers
55 views

Finding if a number is prime by looking at the sum of their digits

Take a number $N = \overline{abcdef...}$ where $a, b, c, d,e,\dots$ are the digits of $N$. Let $k$ be the sum of those digits : $a+b+c+d+e+... = k$ If $k$ is any of ${1, 2, 4, 5, 7, 8 }$ then $N$ ...
2
votes
1answer
21 views

picking coprime numbers from the numbers 1-100

if you choose 51 numbers from the numbers 1-100 inclusive are you guaranteed to have two numbers which are coprime? My thoughts are that you a have to look at the worst case scenarios e.g try to ...
0
votes
1answer
31 views

Can the fundamental solution of a Pell equation be “triangulated” given multiple known solutions?

In this question about “descent” given a single Pell solution, Will Jagy gave the [accepted] answer that, for a Pell equation $$ U^2 - dV^2 = \pm 1, \tag{$\star$} $$ there is no way to determine ...
1
vote
0answers
62 views

IMO 1983 Solution - Day 1 Problem 3

The questions goes as follows: Let $a$ , $b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc - ab - bc - ca$ is the largest integer which cannot ...
0
votes
1answer
59 views

Prove all multiples of $U$ contain all the digits $0$ to $9$

I have to prove that the number $U = 5263157894736842101$ is a "constant number" (that is, every positive multiple of this number contains all the digits from $0$ to $9$ at least one time). In ...
8
votes
1answer
192 views

How to prove that $\frac{1}{x_1}+\frac{1}{x_2}+…+\frac{1}{x_n}-\frac{1}{x_1x_2…x_n}\in \mathbb{N}\cup \{0\}$

Question: Show that for every natural number $n$ there exist $n$ natural numbers $ x_1 < x_2 < ... < x_n ,$ such that $$ ...
1
vote
1answer
29 views

How to invert Euler's totient $\varphi$

I am writing this one since I have struggled a lot, at the very beginning of my Analytic Number Theory Course, to learn how to invert Euler's Totient. I wanted to find an algorithm, but, given the ...
1
vote
1answer
34 views

Number of different vectors.

Let's say that I have a vector with 6 elements. I put two wedges in the vector, i.e., at position 2 and position 6, for instance. And when I say put a wedge, it means... for every time you traverse ...
4
votes
1answer
60 views

A number theory puzzle

I recently came across the following number theoretic puzzle. Suppose I've infinitely many cards, each with a natural number written on it. Given any $n\in \mathbb N$, the number of cards which have a ...
2
votes
2answers
74 views

Equation paramétrique du second degré [closed]

C'est un exercice du concours d'admission en économie de L'Université Protestante au Congo. Voici la question: déterminer la valeur de m pour que la fonction f(x)=(x-7)/(mx²+ mx+m+1) admette deux ...
1
vote
0answers
81 views

Why is $2^{16} = 65536$ the only power of $2$ less than $2^{31000}$ that doesn't contain the digits $1$, $2$, $4$ or $8$ in its decimal representation

$65536$ is the only power of $2$ less than $2^{31000}$ that does not contain the digits $1$, $2$, $4$ or $8$ in its decimal representation. http://en.wikipedia.org/wiki/65536_%28number%29
-2
votes
1answer
53 views

Solve $ (u^n-v^n)=p(u-v)^2$ [closed]

Let $n, u, v,p $ be non-zero positive integers, if $\gcd(u,v)=1$ and $u-v>1$, find all the nontrivial solutions of the Diophantine equation:$$ (u^n-v^n)=p(u-v)^2$$
2
votes
1answer
61 views

Closed form for $\sum_1^\infty 1/p^n$

I was wondering if there are some studies on closed forms for the sum $$\sum_{p \in \mathbb{P}}^\infty \frac{1}{p^n},$$ where $\mathbb{P}$ denotes the set of prime numbers. Obviously I know that ...
2
votes
3answers
34 views

Congruence between binomial coefficient and integer part.

If $p$ is a prime number , prove that $\forall n \in \mathbb{N}, n\geq p:$ $$\binom{n}{p} \equiv \Bigg[\frac{n}{p}\Bigg] (\text{mod }p)$$ where [ ] is the integer part i´been trying this problem ...
0
votes
2answers
50 views

How to show the congruence involving the divisor function

Prove that if $n \in \mathbb{N}$; $n \equiv -1$ $(mod 24)$ $\Longrightarrow $$ \sigma(n) \equiv 0$ $ (mod 24) $ where $\sigma $ is the divisor function. my try: if $n \equiv -1$ $(mod 24)$ ...
2
votes
3answers
49 views

How solve system of congruences?? [closed]

Can anyone help me? $$\left\{\begin{array}{l} 100x - 99y \equiv 2 \pmod{210} \\ 97x + 98y \equiv 3 \pmod{210} \end{array}\right.. $$
1
vote
2answers
36 views

Criteria for $p$ being a prime number.

I'm trying to prove the following problem: $p$ is a prime iff for all $n\in \mathbb{Z}$ with $n\not \equiv 0\mod p$, we have $n^{p-1}\equiv 1 \mod p$. The ($\Rightarrow$) direction is easy: we have ...
2
votes
1answer
32 views

Theory number problem

I need to prove that there are infinitely many natural numbers $n$ for which $2n^2+3$ and $n^2+n+1$ are relatively prime. This is not true for every $n$ (for example, $n=4$), I tried to check for odd ...
1
vote
0answers
52 views

A challenge question in elementary number theory!

Find an expression for the following sum: $$\sum_{i:(i,n)=1}(i-1,n)$$ I guess that this sum equals to $\phi(n)d(n).$
2
votes
2answers
52 views

Number of Relatively Prime Factors

Given a number $n$, in how many ways can you choose two factors that are relatively prime to each other (that is, their greatest common divisor is 1)? Also, am I going in the correct direction by ...
0
votes
0answers
30 views

There are no single perfect square in the sequence 44,444,… [duplicate]

Problem: Prove that there are no perfect squares in the sequence $$44,444,4444,44444,...$$ I know that every perfect square is of the form: $4k$ or$4k+1$. But this test does not work. I've also ...
1
vote
5answers
78 views

How did we find the solution?

In my lecture notes, I read that "We know that $$x^2 \equiv 2 \pmod {7^3}$$ has as solution $$x \equiv 108 \pmod {7^3}$$" How did we find this solution? Any help would be appreciated!
1
vote
1answer
38 views

Sum on digits of powers of two is not too large

Is the following proved: Are there infinitely many positive integers $m$ and an integer $n$ such that sum of digits of $2^m$ is at most $n$?
0
votes
1answer
18 views

Formula For Finding the Next Near Consecutive Perfect Square

For any three consecutive members of a sequence, the first and third members are near consecutive. 1 squared is 1. 2 squared is 4. So 1 and 4 are consecutive perfect squares. 1 squared is 1. 3 ...
2
votes
1answer
46 views

Divisibility Property

I am trying to justify the following result: Let $p,q$ be integers such that $GCD(p,q) = 1$. Then for all $n \in \mathbb{N}$ exists an integer $j_n$ such that $q^{j_n}t = t \ (mod \ p^{2n+1}), \ ...
0
votes
0answers
41 views

Woking Heron's Formula In Reverse

I'm writing a program to generate randomized Heron's Formula word problems. I need to figure out how to work the problem in reverse so that the answer will come out to an integer. As an example, if I ...
0
votes
4answers
59 views

Is there a counterexample to “For all integers $a,b, d$, if $d\mid(3a+2b)$ and $d\mid(2a+b)$, then $d\mid a$ and $d\mid b$.”

I've tried to solve this problem, but I keep getting stuck at the end. Assume $a, b$ , and d are integers and $d$ $\neq$ 0. $3a+2b = dm,\,\,\,$ for some integer $m$. $2a+b = dn,\,\,\,$ for ...
3
votes
2answers
78 views

Divisibility property of $(a+b)^n-a^n-b^n$

Let $n$ be a natural number of the form $n=6k+1$ (while $k$ is a positive integer). Show that $(a^2+ab+b^2)^2$ divides $(a+b)^n-a^n-b^n$ for all integer numbers $a,b$ (such that $a^2+ab+b^2\ne0$).
18
votes
1answer
654 views

Does an elementary solution exist to $x^2+1=y^3$?

Prove that there are no positive integer solutions to $$x^2+1=y^3$$ This problem is easy if you apply Catalans conjecture and still doable talking about Gaussian integers and UFD's. However, can this ...
2
votes
2answers
69 views

Perfect square then it is odd

I have tried several values by trail and error and I concluded the following fact. 'if the $S = 4x^5-4x+1$ is perfect square for some integer $x$, then square root of $s$ is always an odd integer' ...
2
votes
0answers
24 views

On the decimal cycle length.

"If $10$ is a primitive root modulo $p$, the repetend length is equal to $p − 1$... This result can be deduced from Fermat's little theorem, which states that $10^{p−1} = 1\pmod p$." -Wikipedia How? ...
0
votes
3answers
66 views

Proof by induction $n^2 \geq n+1 \ \forall n \geq2$

I have to prove by induction that $n^2 \geq n+1 \ \forall n \geq2$. I have done the following reasoning: the base case is easy to verify; supposing that $n^2 \geq n+1 $ is true, we prove $(n+1)^2 ...
4
votes
1answer
36 views

A positive integer $n$ is prime iff $\varphi(n)! \equiv -1 \pmod n$

Is this proof acceptable ? Theorem 1 (Wilson) A positive integer $n$ is prime iff $(n-1)! \equiv -1 \pmod n$ Theorem 2 A positive integer $n$ is prime iff $\varphi(n)! \equiv -1 \pmod n$ . ...
-1
votes
0answers
55 views

Maximum pairs of men and women

There are shoes of n different colors. We will enumerate the colors from 1 to n. For each i, there are M[i] pairs of men's shoes, W[i] pairs of women's shoes and S[i] pairs of shoelaces of color i. ...
2
votes
8answers
125 views

Find the last two digit of $3^{3^{100}}$.

Find the last two digit of $3^{3^{100}}$. I know how to calculate if I have $3^{100}$. That I will use euler's theorem. which gives me $3^{40}\equiv 1 \pmod{100}$. And so on... but if I have ...
0
votes
2answers
66 views

Day of the week from the date.

I still remember when I was a kid some senior student used to ask us a date from history and then tell us what day was then within 20 seconds. I read montgomery's Number theory and when found the ...
0
votes
0answers
25 views

3D extension of Euclidean algorithm jigsaw method - help!

Recently I've been learning about how the Euclidean algorithm = jigsaw method (filling a rectangle with squares) = forming continued fractions. And today I'm wondering how a 3D version of the jigsaw ...
0
votes
1answer
59 views

How to find solutions in set of intgers?

Is there a simple way to find set of solutions in integers. For example, find integer solution of (1) $x^2 + y = y^5 + x$ (2) what is Extend Ellenberg’s approach? For what type of equations can be ...