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

learn more… | top users | synonyms

0
votes
2answers
24 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
22 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
17 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
1answer
28 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]
4
votes
1answer
58 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
1answer
34 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
35 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
11 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
0answers
28 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
55 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
20 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
31 views

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
8 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
33 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
26 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
14 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
24 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
16 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
14 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
30 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
69 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
39 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
29 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
40 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 ...
1
vote
0answers
42 views

Show that $-1$ is a square $\mod n$, if $n\equiv 1\mod 4$?

I am trying to prove that $-1$ is a square modulo $n$ if, and only if $n\equiv 1\mod 4$. One direction i think i have done... So, we have that $n\equiv 1\mod 4$, from this follows that $n$ must be ...
2
votes
0answers
28 views

A primitive root exists modulo $n$ if and only if $n=2$, $n=4$, $n=p^k$, or $n=2p^k$ with $p$ an odd prime.

I have already proven that primitive roots exist modulo $p^k$ and $2p^k$ for an odd prime $p$. I'm having trouble proving the other direction. Is it simply due to the fact that if $p,q$ are distinct ...
2
votes
1answer
28 views

Different proofs for two squares theorem for primes

There is a proof of two squares theorem for primes of form $4k+1$ from quadratic forms and there is a proof from Bolyai using Gaussian integers. I am reasonably sure such a nice simple statement has ...
0
votes
1answer
18 views

Partial sums of powers of the divisor function

It is easy to establish that $$\sum_{n\le x}\tau(n) \sim n\log n$$ How would one find good bounds on $$\sum_{n\le x} \tau(n)^k $$ for some $k > 0$
2
votes
5answers
69 views

For every natural number $n$, $\gcd(an,bn)=n\gcd(a,b).$

For every natural number I am trying to show that $n$, $\gcd(an,bn)=n\gcd(a,b).$ Here is my attempt. Put $d = gcd(a,b)$; we can write $d=aT+bJ$, where $T$ adn $J$ are integers. Then as $d|a$ and ...
1
vote
0answers
8 views

how to sum the divisors of N mod K if all I have is N mod K?

The input to this problem is N. I have to calculate 2 things: 1 - N! mod (10^9 + 7) 2 - sum of all divisors of N! mod (10^9 + 7) I know how to do the first step, I'm wondering if there is a way ...
1
vote
1answer
76 views

Find all positive integers s.t. $10^m-8^n=2m^2$

Find all pairs of positive integers $(m,n)$ such that $10^m-8^n=2m^2$
2
votes
1answer
44 views

Fermat solved $x^2+2=y^3$ by infinite descent?

In a letter to Christiaan Huygens entitled "on problems in the theory of numbers: a letter to Christiaan Huygens", Fermat claism that he solved the diophantine $x^2+2=y^3$ using infinite descent. Here ...
0
votes
0answers
27 views

Cross relations on number

I have problems finding a method to solve the following problem: Given three relative numbers $p_{1}$, $p_{2}$, $p_{3}$ and three positive numbers $q_{1}$, $q_{2}$, $q_{3}$ we have the following ...
0
votes
1answer
23 views

Use the Euclidean algorithm to prove that gcd(na, nb) = n gcd(a, b).

Assume that a,b,n are all natural numbers. I was going to set it up as: na = q(1)*n(b) + r(1) where a>b and go down the chain: nb = q2 * r(1) + (r2) but something seems off. Someone told me ...
1
vote
1answer
41 views

Use Fundamental Theorem of Arithmetic to prove that if $a >1$, $p$ is prime, and $p|a ^n$ for some $n \in \mathbb{N}$, then $p|a$

So, by the FTOA, since $a >1$, then a can be broken down into a product of a prime factors, so $a = p_1 \times p_2 \times \dotsm \times p_k$. Then, can I say that since $a$ is multiplied by itself ...
0
votes
2answers
41 views

Assume that 495 divides the integer 273x49y5 where x,y ∈ {0,1,2…9}. Find x and y.

So, I know that $495 = 5\times 9\times 11$. So then, if that's the case, then the number $\overline{273x49y5}$ must be divisible by $495$ if and only if it is divisible by 5 and 9 and 11. Then, I ...
0
votes
1answer
48 views

Abstract algebra

Assuming there is a real number $x$ with $ x^3 =7$, prove that $x$ is irrational. I started the proof by contradiction, and I got to the point that $7q^3 = p^3$, but I don't know what should I do ...
0
votes
2answers
34 views

what is the easiest way to show $-1$ is quadratic residue modulo $p=4k+1$?

what is the easiest way to show $-1$ is quadratic residue modulo prime $p=4k+1$? Is there a better way than showing $(2k)!^2\equiv -1 \mod p$?
0
votes
4answers
59 views

Reducing primes in $\mathbb Z[i]$

Let $4k+1=p$ be a prime. Assume you do not know $p=a^2+b^2$(this is what we intend to prove). Over $\mathbb Z[i]$, how does one prove that $p$ splits into conjugates? That is, if $p = ...
1
vote
1answer
30 views

Verify proof that ${p \choose r} ≡ 0 \pmod p$

Let $p$ be a prime number. For any $1 ≤ r ≤ p − 1$, prove that $${p \choose r} ≡ 0 \pmod p$$ I'm thinking that it suffices to show $p$ divides ${p \choose r}$. So then: $$\begin{align} p\ |\ {p ...
0
votes
0answers
10 views

Can irreducible non linear polynomial over $\mathbb{Z}$ have bounded factorization going to infinity?

i've the following question. Suppose that a $f(x) \in \mathbb{Z}[x]$, is such that you have a strictly increasing sequence $\{x_n\}$ of natural numbers such that the primes dividing $f(x_n)$ are all ...
3
votes
2answers
21 views

Math for Computer Science

I have a couple of questions on the material in "Mathematics for Computer Science" by Eric Lehman and Tom Leighton. Q1. This is a theorem in the book: Theorem 24. Let $p$ be a prime. If $p|a_1a_2 ...
0
votes
0answers
8 views

Can this matrix be said to consist of Dirichlet characters?

When: $j=1$ the following formula: $$T(n,k)=\prod\limits_{m=1}_{m \mid n}^{\text{n}} \left(\exp ^{-\mu \left(\frac{n}{m}\right)}\left(\Lambda \left(\frac{n}{m}\right)\right) \chi _{\exp ^{-\mu ...
2
votes
2answers
32 views

If $d$ is a natural number and $d^2$ divides $y^2$ then does $d$ divide $y$?

If $d$ and $y$ are positive integers and I know that $d^{2}|2y^{2}$ then $d^2|2$ (i.e $d=1$) or $d^2|y^2$ . In the case that $d^2|y^2$ does that imply that $d|y$ for all $d,y$ ? Thank you.