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

learn more… | top users | synonyms

-3
votes
3answers
54 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 ...
0
votes
1answer
18 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
27 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
26 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
40 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
0answers
32 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
37 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
12 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
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
79 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
49 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
39 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
79 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
5answers
48 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
26 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
18 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
43 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
68 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
50 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
36 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
13 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
58 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
22 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
38 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
39 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.
0
votes
1answer
25 views

Modular arithmetic - is this a “legal” substitution?

I know that $$a \equiv b ~(\text{mod}~3)$$ and $$c \cdot a \equiv 1 ~(\text{mod}~3)$$ Can I substitute $a$ with $b$? I mean: $$c\cdot b \equiv 1 ~(\text{mod}~3)$$
1
vote
0answers
18 views

Alternating series involving sums of k-primes

As an exercise, if $p_k$ are positive integers composed of k primes including repetition and $\pi_k(n)$ the number of $p_k$ not exceeding n can we show that for the alternating series of sums of ...
-1
votes
0answers
15 views

Inscribed and circumscribed polygons [on hold]

Given a circle, prove (with basic geometric methods: no trigonometry) that the area of any inscribed irregular polygon is strictly smaller than the area of any circumscribed polygon. Extra ...
0
votes
1answer
33 views

Modular Arithmetic Root

Find a cube root of 97mod101 gracefully. I don't really know where to get started...could someone help me? I don't expect you to do the calculations, but could you give me a hint written out in ...
2
votes
4answers
76 views

Last 3 digits of $7^{12341}$

I know that I need to reduce $7^{12341} \pmod {1000}$ By Euler I have $7^{\phi(1000)}\equiv 7^{400}\equiv1\pmod{1000}$ That leaves me with the monster $7^{341}\pmod{1000}$ Is there a way to reduce ...
1
vote
1answer
33 views

Armstrong numbers in base 90

Are there any Armstrong numbers (narcissistic numbers) in base 90? Of course, except the one-digit ones. There don't seem to be. Just curious.
4
votes
1answer
38 views

Prove that $a$ cannot be a prime

The sides of a triangle are of length $a,b,c$ where $a,b,c$ are integers and $a>b$, angle opposite to $c$ is $60$ degrees. Prove that $a$ Cannot be a prime
0
votes
3answers
35 views

$\frac{(n/2)!}{n!} = \frac{1}{2^{n/2}(n-1)!!}$?

I was working on a puzzle involving some rather complex probability when I arrived at two very distinct methods with very different ways of calculating the probability of solving the puzzle. The ...
4
votes
0answers
29 views

Arithmetic Functions: Evaluate $ \sigma(210)$ and $d(63)$

Evaluate $ \sigma(210)$ and $d(63)$ I'm not sure if I got this correct, so here is my attempt. By Theorem 6.3, suppose we have $n=p_1^{\alpha 1}...p_s^{\alpha s}$, then $d(n) =(\alpha_1 ...
0
votes
1answer
41 views

If a|b and b|a, find the value of a in terms of b.

If a|b and b|a, where a and b are integers and a≠0, find the value of a in terms of b. Assume that b>0.
2
votes
0answers
30 views

How would I solve this congruence?

What is the best way to solve this congruence: $r \cdot a^2 = b^3\bmod p$, where $p$ is prime in general? $r$ and $p$ are known, and I want to solve for $a$ and $b$.
3
votes
1answer
42 views

Eulers totient function divided by $n$, counting numbers in the set [1,m] that are coprime to n

If we divide Euler's totient function $\omega(n)$ by $n$, we obtain a fraction. If we multiply this fraction by any natural number $m$ which gives us another natural number $p$, is it true that $p$ is ...