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

learn more… | top users | synonyms (1)

1
vote
2answers
42 views

Does there is a converse for this result, i.e., $Something$⇒ $p$ is a prime

One of the known results in number theory is the following: If $p$ is a prime and if $a$ is any integer, then $$a^{p}\equiv a\pmod{p}$$ My question is: Does there is a converse for this result, i.e.,...
1
vote
0answers
27 views

Is there a difference in the rate of decrease between $f(x)$ and $g(x)$ for increasing $x$?

I have the following two functions of $x$: $ f(x) = \frac{c}{c + (N-1)o + Nd + xl}$ $g(x) = ae + (1-a)\frac{1}{x+2N}$ with $0 \leq a, e, c, o, d, l \leq 1$ and $N, x \in \mathbb{N}^+$. For both ...
15
votes
7answers
3k views
-1
votes
1answer
28 views

Find all primes $p$ such that $z$ is also a prime number

Let $p$ be a prime number. We know that $z=(-√3+2)^{2^{p-2}}+(√3+2)^{2^{p-2}}$ is an integer. My question is: Find all primes $p$ such that $z$ is also a prime number.
1
vote
2answers
64 views

solve this simple equation:$ax^2+byx+c=0$

I need help solving the diophantine equation:$$ax^2+bxy+c=0$$ The quadratic formula does not seem to help much. Please help.
1
vote
1answer
26 views

Find all $x \in\mathbb Z$ such that $16x\equiv 26\pmod{42}$

I got stuck with this seemingly easy problem stated below: Find all $x \in\mathbb Z$ such that $$16x\equiv 26\pmod{42}$$ I tried the following: $$ 16x \equiv 26 \pmod{42}\Longleftrightarrow 42 \...
1
vote
1answer
100 views

Proving congruence class

Let $a$ and $m$ be integers such that $m ≥ 1$. Consider the congruence class of $a$, $[a]$ modulo $m$. It follows that $∀ x ∈ [a], \gcd(x, m) = \gcd(a, m)$. I have my algebra midterm in two days! ...
4
votes
1answer
131 views

Integer solutions of $a^3+2a+1=2^b$

What are the solutions in integers of $a^3+2a+1=2^b$? [Source: Serbian competition problem]
0
votes
1answer
41 views

The primes such that removing digits from the right end leaves another prime

The number 73,939,133 is prime. Keep removing a digit from the right end. Each of the remaining numbers is prime. How to find other numbers with this property?
2
votes
1answer
38 views

Does there exist a sequence $(S_i)_{i=1}^{\infty},\ S_i=\pm1$ such that $\forall i(2+S_1g_1+S_2g_2+\cdots+S_ig_i\in\Bbb P)\wedge\exists i:S_i=-1$?

Consider a sequence $(S_i)_{i=1}^{\infty},\ S_i=\pm1$ other than $\{1,1,\ldots\}$. Let $g_i=p_{i+1}-p_i$, where $p_i$ is the $i$th prime. Is it possible that for all $k\in\Bbb Z^+,\ 2+\sum_{i=1}^...
2
votes
1answer
83 views

Coprime numbers and equations

Suppose $~m~$ and $~n~$ are coprime and both of them are greater than one. Is it right that equation $~mx + ny = (m-1)(n-1)~$ has solutions over non-negative integers? For example $~ (x,y) = (6,0) ~...
4
votes
1answer
41 views

Submagmas of natural numbers

What is known about submagmas of natural numbers under addition/multiplication? For example, all subgroups of integers under addition are of the form $~n \mathbb{Z}~$. Are there similar results for ...
10
votes
1answer
486 views

Books to read to understand Terence Tao's Analytic Number Theory Papers

I tried to understand Terence Tao's Analytic Number Theory Papers. For example, this paper, Every Odd Number Greater Than 1 is The Sum of at Most Five Primes. Which books shall I read to prepare ...
1
vote
2answers
163 views

For every prime of the form 6x-1 are there comparable number of primes of the form 6x+1

All primes except $2$ and $3$ are of the form $6x-1$ and $6x+1$. For every prime of the form $6x-1$ are there comparable number of primes of the form $6x+1$ in the first $10000$ primes or is there an ...
1
vote
0answers
33 views

Getting a decomposition of an integer

Firstly, I need to admit that my English is quite poor. Ok. I've got a problem- how can I get any possible decompositions of a given integer? Sample decomposition: $$\begin{align} 30&=1^2+2^2+5^2=...
1
vote
1answer
27 views

Let $\{A_n\}_{n=1}^\infty$ be a sequence of nonempty subsets of $\mathbb{Z}$, which of the following is uncountably infinite?

Let $\{A_n\}_{n=1}^\infty$ be a sequence of nonempty subsets of $\mathbb{Z}$. Which of the following is uncountably infinite? A) $A_1$ B) $\bigcap_{n=1}^\infty A_n$ C) $\bigcup_{n=1}^\infty A_n$ D)...
2
votes
3answers
114 views

Prove that $(\sqrt3+2)^m$ is not a natural number for all natural numbers $m≥1$

The aim of this question is to show this lemma: Prove that $(√3+2)^{m}$ is not a natural number for all natural numbers $m≥1$.
1
vote
4answers
47 views

Use Induction to prove: $(1+2x)^n \geq 1+2nx$

Show by induction that: for all $x>0$ that $(1+2x)^n \geq 1+2nx$ So far I have: for $n=1 \rightarrow (1+2x)^1 \geq 1+2x$. True! for $n=k+1 \rightarrow (1+2x)^{k+1} \geq 1+2(k+1)x$ ...
2
votes
2answers
63 views

Discrete Math Proof Method

Give a direct proof of the fact that $a^2-5a+6$ is even for any integer $a$. Suppose $a$ and $b$ are integers and $a^2-5b$ is even. Prove that $b^2-5a$ is even.
17
votes
3answers
4k views

Largest prime number with all digits different

What is the largest prime with distinct digits? (It is certainly less than ten digits long.Can you explain it why?
2
votes
0answers
52 views

Prerequisites: Dirichlet Lectures Number Theory

I am interested in getting Dirichlet's Lectures in Number Theory but I'm afraid I don't know that much advanced math. Do I need to know things like Determinants for this book? Any list of ...
2
votes
1answer
101 views

Number of $0$ in the end of $11^n-1$

$n$ is integer, calculate number of $0$ in the end of $11^n-1$(i.e. largest integer $m$ such that $10^m|11^n-1$). The original question was $n=100$ and I could only choose $m$ from 1 to 5. I ...
2
votes
0answers
53 views

Prove that exist set $B$: $|B|\ge 2014$ .

For $A$ is a set has $2014$ natural numbers. Prove that exist a set $B\subset \mathbb{N}$ such that $A\subset B$ and sum square of all elements of $B$ equal area of all elements of $B$. I think we ...
2
votes
1answer
45 views

An equation which has solution modulo every integer

In the book Abstract Algebra by Dummit and Foote he remarks that there is an equation which has solutions modulo every integer but has no integer solutions. The equation he gives is $$3x^3+4y^3+5z^3=0$...
1
vote
0answers
64 views

Does there exist a positive integer which is a power of two, such that by rearranging it's digits we can get another power of two?

Does there exist a positive integer which is a power of two, such that by rearranging it's digits we can get another power of two? I know a quite good solution, that involves working with sum of ...
2
votes
2answers
75 views

If $n$ is composite then $n$ divides $(n-1)!$ [duplicate]

We need to prove that if $n$ is a composite number $>4$, then $n|(n-1)!$. I wanted to ask if my observation is correct or not. What I think is that the statement can be reduced to $n|(n-2)!$ ...
3
votes
1answer
52 views

A finding (?) about some primitive Pythagorean triples

I have just stumbled on the fact that the sum of the three absolute differences between each pair of a primitive Pythagorean triple [absolute values of (a-b), (b-c) and (c-a), where a,b,c constitute ...
1
vote
1answer
74 views

Proving property of congruence - help needed

Let $c,d,m,k ∈ \mathbb{Z}$ such that $m ≥ 2$ and $k$ is not zero. Let $f = \gcd(k,m)$. If $c \equiv d \pmod m $ and $k$ divides both $c$ and $d$, then $$ \frac{c}{k} \equiv \frac{d}{k} \left({\...
0
votes
2answers
40 views

The sum of n numbers that cube to one is congruent modulus three.

Assume $a_1,\dots,a_n\in\mathbb C$ cube to give one. Assume $\sum a_i=\sum a_i^2$. How can we see that $\sum a_i\equiv n(mod3)$? May the sum be different than $n$?
1
vote
1answer
62 views

Using Hensel's lemma to solve congruence?

I'm trying to use Hensel's lemma to solve the congruence $$x^3 + x^2 - 5 \equiv 0 \pmod{7^3}$$ I begin by solving $$x^3 + x^2 - 5 \equiv 0 \pmod{7}$$ and observe that $x \equiv 2 \pmod{7}$ is the ...
1
vote
3answers
157 views

Example involving the Chinese Remainder Theorem

I am working on a Number Theory book and I have come across the following problem: (Underwood Dudley 2nd Edition Section 5 Problem 3): Solve the system: x $\equiv 3(mod 5)$ x $\equiv 5(mod7)$ x $\...
0
votes
2answers
43 views

$27 | (2x+1)^2 \implies 2x$ is a multiple of 9?

Found this simple fact in a proof that I was looking up, and am confused as to why it is true: Why does $27 | (2x+1)^2 \implies 2x + 1$ is a multiple of 9?
-2
votes
3answers
1k views

The sum of all the odd numbers to infinity [duplicate]

We have this sequence: S1: 1+2+3+4+5+6.. (to infinity) It has been demonstrated, that S1 = -1/12. Now, what happens if i multiply by a factor of 2? S2: 2+4+6+8+10+12.... (to infinity). I have 2S1,...
1
vote
1answer
31 views

Show that $p^{q^3+q} = p^2$ (mod $q$)

For two distinct primes $p,q$, show that $p^{q^3+q} = p^2$ (mod $q$). Since $gcd(p,q)=1$, it suffices to show that $pq|p^{q^3+q}-p^2$, since $p$ obviously divides that, but I don't know how to ...
1
vote
7answers
110 views

Prove that $gcd(a, b) = gcd(b, a-b)$

I can understand the concept that $\gcd(a, b) = \gcd(b, r)$, where $a = bq + r$, which is grounded from the fact that $\gcd(a, b) = \gcd(b, a-b)$, but I have no intuition for the latter.
1
vote
2answers
148 views

Inductive proof of the identity $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ [duplicate]

I'm trying to prove the following identity: $$\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$$ I need to prove it using induction (not a counting argument), I ...
4
votes
1answer
43 views

Find $a$ given some additional conditions

The problem is: If $x+y+z=3$ and $xy+xz+yz=a$, where $a$ is a real number, find $a$ if the difference between the maximum and minimum value of $x$ is $8$. So what I did was use Vieta's equations ...
1
vote
1answer
18 views

Arithmetic Using Different Bases

If $Feed_{base 8}-Feed_{base 5}=Feed_{base 7}$, then what do the digits $F, e$, and $d$ stand for? So far I have that $d = 5$ and $e = 6$. I think those are correct. However, I am getting stuck on ...
1
vote
2answers
367 views

Find the number of three digit numbers with a even number of positive divisor

I guess the question is probably just asking for the number of the three digit composite numbers besides the perfect square. So the question critical to solving the problem is really how to find ...
3
votes
2answers
65 views

If for all $n\in\Bbb{N}, a^n-n$ divides $b^n-n$ then $a=b$.

Exercise: Let $a,b\in\Bbb{N}$, show that if for all $n\in\Bbb{N}, \quad a^n-n$ divides $b^n-n$, then $a=b$. I don't have lot of knowledge on this subject, I am aware about some elementary result but ...
0
votes
1answer
181 views

how to predict the sum of digits of the number $A(n)$ for a large natural $n$ without calculation, when $A(n)=a(n^2+n)+b$?

look $A(n)=9n^2+9n-1$ , let $n=15233$ , $A(15233)=2088535697$ the sum of digits of this obtained number is :$53$ and always take this form :$9k+8$ , where $k=5$ and always exist a natural number $k$ ...
0
votes
1answer
61 views

Clarification of Legendre's theorem re: $ ax^2+by^2=cz^2$

Theorem (Legendre): Let a,b,c coprime positive integers, then $ax^2+by^2=cz^2$ has a nontrivial solution in rationals x,y,z iff $(−bc/a)=(−ac/b)=(ab/c)=1$. I read this somewhere. Is it really the way ...
2
votes
2answers
164 views

Which theorem could be used?

I want to write the $p-$adic expansion of $6!$ in $\mathbb{Q}_3$. I have to solve the congruence $x \equiv 6! \pmod {3^n}$, right? I found the following: $$x_0 \equiv 6! \pmod 3 \Rightarrow x_0 \...
3
votes
2answers
439 views

If $P$ and $Q$ are distinct primes, how to prove that $\sqrt{PQ}$ is irrational?

$P$ and $Q$ are two distinct prime numbers. How can I prove that $\sqrt{PQ}$ is an irrational number?
0
votes
1answer
36 views

Prove the divisors pairs

If we arrange the positive distinct divisors of a number A by increasing order, then we get something like: $$1<a_1<a_2<a_3<...<a_{n-2}<a_{n-1}<a_n<A$$How can we prove that $$...
0
votes
5answers
84 views

Do there exist integers s and t such that 11s + 9t = 1?

Do there exist integers s and t such that 11s + 9t = 1? We just started learning discrete mathematics and I am absolutely stuck with proof questions. Does this question belongs to number theory ...
-1
votes
4answers
132 views

Prove that $x^2 + y^2 = 3(z^2 + m^2)$ has no solutions in integer [closed]

Prove that: $$ x^2 + y^2 = 3(z^2 + m^2) $$ has no solutions in integer Except $0 0 0 0$
-1
votes
1answer
472 views

Find $n$ such that $n/2$ is a square, $n/3$ is a cube, and $n/5$ a fifth power

Consider the set of positive integers $n \in \mathbb {Z}>0$ such that $\dfrac{n}{2}$ is a perfect square, $\dfrac{n}{3}$ is a perfect cube, and $\dfrac{n}{5}$ is a perfect fifth power; that is to ...
1
vote
1answer
126 views

Proof of a sum of positive divisors

Let $n$ be an integer greater than zero. Prove $$(\sum_{d|n}v(d)){}^{2}=\sum_{d|n}(v(d))^{3}$$ where $v(d)$ is the number of positive divisors of $n$. I'll outline what my problem is. I write $n= ...
1
vote
2answers
221 views

Two math professors problem

My friend asks me a question from internet. The question is as follows Two math professors, professor Uno and professor Dos, play chess at the park while reminiscing about their past. Prof. ...