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

learn more… | top users | synonyms

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
31 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
44 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
43 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
26 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
70 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
48 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
29 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
44 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
35 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
60 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
31 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
11 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
9 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.
-4
votes
0answers
34 views

Revisiting 0.99999… and more [closed]

Do you agree or not? Those who look for duplicate posts to this one might find this on the post that asks: “I'm told by smart people that 0.999999999...=1 and I believe them, but is there a proof ...
1
vote
3answers
73 views

If $x^2$ is divisible by $4$ then $x$ is even?

I am studying discrete mathematics as course and I have to prove this "If $x^2$ is divisible by $4$ then $x$ is even". I am wondering how to prove it using the contrapositive of this ...
0
votes
2answers
16 views

finding the largest term in a binary summation

I'm working on a problem that involves the following summation: $$y=\sum_{i=0}^{x}i2^i$$ I need to determine the largest value of $x$ such that $y$ is less than or equal to some integer K. Currently ...
0
votes
1answer
13 views

Rings with zero-divisors

this might be an odd question but I know that in a ring with no zero-divisors $ac|bc$ implies $a|b$, if $c\neq 0$. So are there Rings with zero divisors where $ac|bc$ still implies $a|b$? Thank you.
2
votes
0answers
53 views

Conjecture on sum of powers

Let $n$ be an odd number, $x,y$ integers and $p$ a prime number. Now, suppose that $p\ne n$ and $$ p|\frac{x^n+y^n}{x+y} $$ Then, I have been observed that $p \equiv 1 \pmod{n}$. This is, all of the ...
0
votes
1answer
18 views

Would someone please explain this argument? (Legendre formula)

Here is an argument in my book. Theorem If $n$ is a positive integer and $p$ is a prime, then the exponent of the highest power of p that divides $n!$ is $\sum_{k=1}^\infty [\frac{n}{p^k}]$ ...
1
vote
2answers
50 views

Prime numbers and $\sqrt{10301}$

On my exam recently, we had the following question: Use the prime number theorem to estimate the number of primes less than $\sqrt{10301}$, and hence, give a concise argument whether 10301 is prime ...
1
vote
1answer
22 views

Proofs of the following gcd Theorems.

Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$. Theorem 2: Let $a$ and $b$ be nonzero integers. The ...
1
vote
1answer
60 views

Triplets of distinct integers > 1 that return integer values.

If $(A, B, C)$ are distinct integers $> 1$, and $$f(A, B, C) = \frac{\frac{A^2-1}{A} + \frac{B^2-1}{B}}{\frac{C^2-1}{C}},$$ then for what (if any) triplets $(A, B, C)$ is $f(A, B, C)$ an integer? ...
0
votes
0answers
15 views

Why is $k^n \equiv 0 (mod k^2)$ in this case?

It is written in my text that: Let $n$ be an absolute Fermat pseudoprime. Claim : $n$ is square free Suppose there exists $k>1$ such that $k^2$ divides $n$. Since $n$ is an absolute ...
2
votes
3answers
48 views

How to prove that $\gcd(2n+3, 3n+1)$ divides $7$?

How can I start proving that gcd(2n+3, 3n+1) | 7? EDIT: It is $\gcd(2n+3, 3n+1)$ divides $7$. My bad. Thanks paw88789.
1
vote
0answers
27 views

Generalization of Hensel's lemma

I've been trying to prove the following generalization of Hensel's lemma: Let $ f\in \mathbb{Z}[x_1, \dots, x_n] $ and $ f=0 $ be a diophantine equation. Let's assume that for some $ d \in ...
0
votes
1answer
32 views

Find out $f(n)$ where n is an integer

Suppose I need a function $f(n)$ such that $f(n)$ is odd when $n=4,12,20,28...$ and even when $n=8,16,24,32...$. Then the answer would be $f(n)=\frac{n}{4}$. Similarly, now suppose I need $f(n)$ such ...
12
votes
2answers
157 views

Integer solutions of $x^3-x+9=5y^2$

What are the solutions in integers of $x^3-x+9=5y^2$? [Source: Hungarian competition problem]
1
vote
1answer
24 views

About primitive roots.

Assuming 6 is a primitive root mod p ( for some odd prime p) ( assuming this is possible) then could p have another distinct primitive root n (such that 1 < n < (p-1)) where 2 | n? ( n not equal ...
1
vote
2answers
72 views

How to find all cyclic quadrilaterals with integer sides?

We need to find all cyclic quadrilaterals (or formulas that gives its sides), which have integer sides $a,b,c,d$. The constrain is that its area must be an integer multiple of its perimeter. We can ...
0
votes
1answer
30 views

If $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$, then $ab \pmod 3 \equiv 2$

I'm stuck on this this problem: Let $a$ and $b$ be positive integers with $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$. Prove that $ab \pmod 3 \equiv 2$. I think the first step for the direct ...
2
votes
1answer
30 views

Definition of field of fractions of $p$-adic integers

I am given this definition of the field of fractions of the p-adic integers: $$Q_p=\left\{ \frac{r}{s} \mid r, s \in Z_p, s \neq 0\right\}$$ How can I show that: $Q_p$ consists of the sums of the ...
0
votes
0answers
19 views

Calculate sum of distinct pairs [closed]

Given an array A we need to find the sum of all distinct pairs of indexes from the array and adds the value ⌊$A[i]+A[j]\over A[i]×A[j]$⌋ to the sum Note: ⌊$A\over B$⌋ is the integer division ...
1
vote
2answers
32 views

figure out $f(n)$ under given conditions

Suppose I need a function $f(n)$ such that $f(n)$ is odd when $n=4,12,20,28...$ and even when $n=8,16,24,32...$. Then the answer would be $f(n)=\frac{n}{4}$. Similarly, now suppose I need $f(n)$ such ...
2
votes
0answers
24 views

find other sums similarly under sum

In the under sum there exists all number 1,...,9. Similarly write at least 10 sums other. $$659+214=873.$$ For example we can write $259+614=873$ or $619+254=873$ or $596+142=738$. Do there exists a ...
2
votes
4answers
51 views

How to find the $n$th term of a repeating pattern

What is the nth term of following sequence $1,2,3,4,5,6,1,2,3,4,5,6,\ldots$ $(n, n+1, n+2, n+3,\ldots,$ $,n+p, n, n+1, n+2, n+3,$ $n+4, n+5,$ $\ldots,$ $n+p,$ $n,$ $n+1,$ $\ldots)$ Actually, I am ...
3
votes
4answers
101 views

Prove that $2^{10}+5^{12}$ is composite

Prove that $2^{10}+5^{12}$ is composite I need to solve this using only high school mathematics. Any ideas?