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

learn more… | top users | synonyms

3
votes
0answers
8 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 ...
0
votes
0answers
19 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 ...
0
votes
0answers
27 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
0answers
26 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 ...
1
vote
1answer
30 views

if n is composite n divides (n-1)!

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)! Because n and n-1 ...
-1
votes
2answers
38 views

Find the number of natural numbers less than 2014 which are neither squares nor cubes [on hold]

Find the number of positive integers less than 2014 that are neither squares nor cubes.
3
votes
1answer
27 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 ...
0
votes
2answers
26 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
20 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
19 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
38 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
63 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 ...
1
vote
1answer
21 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 ...
4
votes
0answers
30 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
15 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
28 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 ...
0
votes
0answers
7 views

one-to-one correspondence with a set of primitive dirichlet charchter

Let $$\operatorname{Prim}_{N}=\{\xi \mid \xi \text{ a primitive Dirichlet charchter mod } F \text{ with } F\mid N\}$$ and $$\operatorname{Char}_{N}=\{\xi" \mid \xi" \text{ Dirichlet charchter mod } N ...
4
votes
2answers
43 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 ...
0
votes
1answer
38 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
39 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 ...
1
vote
0answers
14 views

Solution of Pell equation over field of p-adic numbers

Right now I am studying Pell equation. Using continued fractions, we can find the solution of Pell equation. Now my question, is it possible for me to find a solution in the field of p-adic numbers ...
0
votes
0answers
20 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 ...
1
vote
2answers
33 views

How can I prove that the square root of two prime numbers multiplied is non-rational number?

$P$ and $Q$ are two distinct prime numbers. How can I prove that $\sqrt{PQ}$ is an irrational number?
1
vote
1answer
27 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
83 views

Showing $p^2 + q^2\ne r^2$ for primes $p, q, r$. [on hold]

Let $p$, $q$, $r$ be prime numbers. Show that $p^2 + q^2\ne r^2$.
0
votes
5answers
66 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 ...
0
votes
1answer
52 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
42 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
84 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. ...
0
votes
2answers
17 views

Finding the closed form of a multiplicative function

Let $n$ be an integer and $n>0$. Define function $g$ by $g(1)=1$ and $g(n) = 2^{m}$, where $m$ is the number of distinct prime numbers in the prime factorization of $n$. I've already proven that ...
0
votes
6answers
53 views

How to know a number is divisible by a given number without using a calculator?

My question is simple and comes from my curiousity during studying math. How to know a number is divisible by $7$ or $13$ without using a calculator? For example, how do we decide intuitively that ...
2
votes
0answers
40 views

integral solutions of $ ax^2+by^2=c$

Let $a,b,c,x,y$ be all non-zero positive integers, $\gcd(a,b,c)=1$, find the integral solutions of:$$ ax^2+by^2=c$$ Any hint?
0
votes
2answers
26 views

Show that in the sequence b,2b,3b…,mb there are exactly gcd(b,m) numbers divisible by m.

"Where b and m are integers and m is bigger than one, show that in the sequence b,2b,3b...,mb there are exactly gcd(b,m) numbers divisible by m. I'm having a real hard time proving that... can anyone ...
1
vote
0answers
27 views

Fundamental Theorem of Arithmetic (Canonical) missing crucial step

I've worked long on the proof of the fundamental theorem of Arithmetic and there is only one tiny piece left I can't wrap my head around. Suppose that $$\prod_{i=1}^r p_i^{m_i} = \prod_{j=1}^s ...
2
votes
0answers
19 views

Symmetric Fibonacci images

I was playing with the Turtle module in Python and decided to try plotting the Fibonacci series with the following scheme where $f_n$ is the $n^{th}$ Fibonacci number: Rotate the turtle $k (f_n ...
4
votes
0answers
52 views

Floor function inequality $\lfloor a\sqrt{2}\rfloor\lfloor b\sqrt{7}\rfloor <\lfloor ab\sqrt{14}\rfloor$

Let $a,b$ be positive integers. Show that $\lfloor a\sqrt{2}\rfloor\lfloor b\sqrt{7}\rfloor <\lfloor ab\sqrt{14}\rfloor$. [Source: Russian competition problem]
5
votes
1answer
69 views

77 is the greatest integer that cannot be a finite sum of distinct integers greater than 1 whose sum of their reciprocals is 1

In 1963, Ron. Graham proved on a short article entitled "A Theorem on Partitions" (it can be found in the web) that every positive integer greater than $ 77 $ is a finite sum of distinct integers ...
3
votes
2answers
51 views

If $(a^2+b^2) \mid (c^2+d^2)$ and $\gcd(a,b)=\gcd(c,d)=1$ and $\gcd(a,c)>1$, what can be said about the components?

While working on a divisibility problem in integers $a,b,c,d$, with $\gcd(a,b)=\gcd(c,d)=1$, I've come up against the hypothetical condition $$ (a^2+b^2) \mid (c^2+d^2), \tag{$\star$} $$ where, also ...
0
votes
1answer
37 views

What are the nonegative integral solutions to $k^2 = 2 n^2 +1$?

What are the nonegative integral solutions to $k^2 = 2 n^2 +1$? $n = 2$ and $k = 3$ works, what is the next smallest pair?
0
votes
0answers
14 views

How can we solve the module function related equation?

Suppose that $\alpha,\beta=1,2,\cdots,n_1n_2$, and they satisfy the equation $$ \beta-\textbf{mod}(\beta,n_2)=\alpha-\textbf{mod}(\alpha,n_2) $$ where $\textbf{mod(,)}$ is the module function as usual ...
0
votes
2answers
61 views

Can Legendre's theorem really help solve this equation: $ax^2+by^2=cz^2$?

let $a,b,c,x,y$ be non-zero positive integers such that $$\gcd(x,y,z)=1$$ $$ \gcd(x,a)>1$$$$ \gcd(y,b)>1$$ $$ \gcd(z,c)>1 $$ If $a,b,c$ are square-free, find all the non-trivial integral ...
3
votes
1answer
59 views

Is this number composite or prime: $2000^{2002} + 2000^{2000} + 1$?

Is this number composite or prime? $$2000^{2002} + 2000^{2000} + 1$$ I want to find an easy approach to this problem.
1
vote
0answers
24 views

how to find if a number has a representation in a powerbase format?

I better explain this problem with an example, $100$ would be represented as $983$ because $9^1 + 8^2 + 3^3$ is one hundred. So how to find the relation between the number $n$ and numbers that can be ...
0
votes
1answer
39 views

Formal solution needed to question that looks too easy to be true about the Gauss map

Using the itineraries of the Gauss map write the continued fraction expansion of the number $0 \leqslant \alpha \leqslant 1$ such that $$\displaystyle \alpha = \dfrac{1}{4+\dfrac{1}{3+\alpha}}$$ I ...
-1
votes
0answers
20 views

Redefining numbers [on hold]

Let's say we have : 1 = 50 45 = 120 Then how can I know 12 = ? And more globally any number x = ? I don't know why but I can't find the answer to this problem. Thanks for your help!
0
votes
0answers
9 views

Using the Hasse Principle to find Integer Points

How can we use the Hasse Principle to find integer solutions to an equation (quadratic form)? According to the Wikipedia article http://en.wikipedia.org/wiki/Hasse_principle, the Hasse principle can ...
1
vote
0answers
41 views

Is this an application of the Chinese Remainder Theorem?

I've been having some issues with the following problem for a few days, and I think I might have found the answer, but I'm not quite sure: Problem: Let f(x) be a polynomial with integer coefficients. ...
0
votes
1answer
29 views

How do I prove that $\sum_{k=1}^{b-1} [k \frac{a}{b}] = \frac{(a-1)(b-1)}{2}$?

Let $a,b$ be relatively prime positive integers. Then, how do I prove that $\sum_{k=1}^{b-1} [k \frac{a}{b}] = \frac{(a-1)(b-1)}{2}$? Please give me some hints..
0
votes
0answers
28 views

Equation with gcf , lcm

Can you please help me with this? I have no idea how to solve this problem Find all positive integers $a$, $b$ such that $$a+b+\gcd(a,b)+\text{lcm}(a,b)=50$$ Thank you for answer
1
vote
1answer
15 views

reducing the modulus of a Dirichlet character

Let $\chi$ be a Dirichlet character modulo $N$. Let $M$ be a positive divisor of $N$ such that $$\text{radical}(N)=\text{radical}(M).$$ Is $\chi$ be a character modulo $M$? Best regards.