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

learn more… | top users | synonyms

1
vote
2answers
42 views

Finding a two-digit number.

The sum of the digits of a two-digit number is $9$. When we intrchange the digits,it is found that the resulting new number is greater than the original number by $27$. What is two digit number?
0
votes
2answers
34 views

Finding number given least common multiple with $24$

Is there any easier or algorithmic method to solve this problem? There are two numbers, $n$ and $6$. The least common multiple of $n$ and $6$ is $24$. Find $n$. The way I do this is by ...
1
vote
1answer
37 views

If $n$ is any positive integer whose last digit is $5$, then $5$ divides $n$

Prove that if n is any positive integer whose last digit is a 5, then 5|n Therefore, n is going to be 5, 15, 25, 35 etc ... b∣a states that 'b divides a' and we know that 5∣5, 5∣15, 5∣25, 5∣35 ...
3
votes
3answers
76 views

Proof by induction: $n$th Fibonacci number is at most $ 2^n$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$ My Proof: Base case: $n = 1$ $\operatorname{fibonacci}(1) \le 2^ 1$ ...
1
vote
0answers
58 views

A sequence of subsets of $\Bbb Z$ not containing nontrivial subgroups

Is there a sequence $(A_n)$ of subsets of $\Bbb Z$ such that always $\{a-b\mid a,b\in A_{n+1}\}$ is a proper subset of $A_n$ and no $A_n$ contains an infinite subgroup of $(\Bbb Z,+)$?
7
votes
5answers
609 views

Is the product of uniformly distributed numbers, uniformly distributed too?

My question is simple, I think. If we took two random natural numbers $a$ and $b$ uniformly distributed in a specific range $[c,d]$, is $ab$ a uniformly distributed too? What if $a$ and $b$ are not ...
1
vote
2answers
35 views

Proof of an equality involving $\phi(n)$

I would like to prove the following equality: $$k^{\phi(l)} + l^{\phi(k)} \equiv1\pmod{lk}$$if $\gcd(l,k)=1$. What methods can I use? Thank you for your help.
3
votes
4answers
68 views

Let $n \in \mathbb {Z}$. If $n^2$ is even, then $n$ is even.

I think that a proof by contrapositive can do, but I don't know how to complete it. Assume that $n$ is odd. Then, $n=2k+1$ for some integer $k$. Therefore, $n^2= (2k+1)^2 = 4k^2+4k+1$. I know that ...
6
votes
3answers
126 views

Towards a formula for the Euler $\phi$ function?

$\Phi_n(1)$ and $\Phi_n(-1)$ for the cyclotomic polynomials are well-known. I am now looking for $$\Phi_n(i)$$ and/or $$\Phi_n(-i)$$ with $i$ the complex unit. The reason is : I suppose it is ...
0
votes
2answers
37 views

How to solve equation in complex numbers?

For $n$ odd ( e.g. with $n\equiv 1\mod 4 )$ I seek a solution $f(n)$ for this simple equation in the complex numbers $$(-1)^{f(n)}2^{\frac{n-1}{2}}=-\frac i2(1+i)^{n+1}$$ $f(n)$ is probably an integer ...
0
votes
0answers
42 views

Number of prime factors of Mersenne numbers

Let $p$ be a prime and let $M_p = 2^p-1$. Is it known whether the number of prime factors of $M_p$ is unbounded above as $p \to \infty$? Also do the probabilities estimating the chance that $M_p$ is ...
5
votes
1answer
105 views

Fermat: Prove $a^4-b^4=c^2$ impossible

Prove by infinite descent that there do not exist integers $a,b,c$ pairwise coprime such that $a^4-b^4=c^2$.
2
votes
3answers
102 views

Solution of equation $ x^2\equiv 1 \pmod{784}$

How to solve the equation $ x^2\equiv 1 \pmod{784}$ ? Context I know the Chinese Remainder theorem, but have no idea how to begin. Could you give me any clue? The only thing that I would like to is ...
3
votes
1answer
50 views

Why do we assume relatively primes?

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$? Why do we assume that $$(m,61) = 1\wedge (n,61) = 1 $$ ? I mean why it is possible ?
3
votes
2answers
70 views

prove/verify prime division

$a_i$ positive integers for $1\le i\le n$ if $p$ prime and $p\mid a_1a_2\cdots a_n$ then $p\mid a_i$ for some $1\le i\le n$: My thinking is to prove it by contraposition. $p$ does not divide ...
4
votes
1answer
68 views

Solving $x^2 - 11y^2 = 3$ using congruences

I'm looking to find solutions to $x^2 - 11y^2 = 3$ using congruences. The question specifically asks "Can this equation be solved by congruences (mod 3)? If so, what is the solution? (mod 4) ? (mod ...
2
votes
2answers
39 views

Proof: no fractions that can't be written in lowest term with Well Ordering Principle

My question is the exact same question as the one in this post but I commented on it but it's from a year ago so I just wanted to bump it and see if I could get a response: Prove that there's no ...
4
votes
4answers
95 views

Remainder when $11^{2402}$ is divided by $3000$? [closed]

What is the remainder when $11^{2402}$ is divided by $3000$? I just came across this question. I am a beginner in number theory. Your help would mean a lot.Thanks!!
-1
votes
2answers
174 views

Bored natural numbers

This is my problem If $a$ for $n$ times , $b$ for $m$ times , $a,b\in\{1,2,..,9 \}$, $n,m\in \mathbb{N}^*$, $n\neq m$ proof that $$ \underbrace{aaa\cdots aaa}_{n\ \small\mbox{times} }\, \cdot\, ...
4
votes
1answer
33 views

Numbers with the property $\overline{a_1a_2a_3a_4\dots a_n}=a_1+a_2^2+a_3^3…a_n^n$

I have a couple of questions about numbers that satisfy a certain property. The numbers have the property that $\overline{a_1a_2a_3a_4\dots a_n}=a_1+a_2^2+a_3^3...a_n^n$ where ...
1
vote
4answers
72 views

Prove that if one of the numbers $(2^n)-1$, $(2^n)+1$ is prime, then the other is composite. [duplicate]

Let n be an integer greater than 1. Prove that if one of the numbers $$2^n-1, 2^n+1$$ is prime, then other is composite.
3
votes
0answers
30 views

Predicting the Order of Quadratic Residues

Using Euler's criterion we can tell if an integer is a quadratic residue modulo a prime. For example, if the prime was 11, then we could test the integers from 1 to 10 and determine that 1, 3, 4, 5, ...
6
votes
3answers
93 views

If $n=3^{2^k}-2^{2^k}$, then $n\mid 3^{n-1}-2^{n-1}$

Let $k \in \mathbb{N}$ and let $n=3^{2^k}-2^{2^k}$. Show that $$n\mid 3^{n-1}-2^{n-1}.$$ I have no idea how to prove this. Any suggestions?
0
votes
0answers
28 views

Bézout's identity Application

I am trying to prove the following lemma: Let $n,m$ be positive integers, and let $d = GCD(m,n)$. Let $c,r$ be positive integers s.t. $d = cm - rn$ If $c > dn $, then for every two positive ...
2
votes
0answers
39 views

How to prove: $pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$

For any two distinct primes $p, q$ there is a unique integer $k$ such that: $$pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$$ Where $k$ is the smallest integer greater than $p$ that is relatively ...
1
vote
3answers
65 views

exponent of $p$ in the prime factorization of $n!$

exponent of $p$ in the prime factorization of $n!$ is given by $\large \sum \limits_{i=1}^{\lfloor\log_p n \rfloor } \left\lfloor \dfrac{n}{p^i}\right\rfloor $. can this sum be simplified further to ...
1
vote
0answers
37 views

order of x mod p(x) in Z2

I am writing a software that analyze the behavior of an LFSR given its feedback polynomial. At some point, I need to compute the order of x mod p(x) in Z2. In mathematical terms I am looking for the ...
3
votes
2answers
55 views

Chinese Remainder Theorem Question

Show that: x ≡ 6(mod 9) x ≡ 5(mod 7) x ≡ 12(mod 10) Has a unique solution modulo 630. Step 1: GCF(9,7) = 1 GCF(9,10) = 1 GCF (7,10) = 1 Step 2: 9 x 7 x 10 = 630 Step 3: c1 = 630/9 = 70 c2 = ...
1
vote
4answers
46 views

Linear Diophantine equation $3x + 5y = 11$

Solve the Diophantine equation $3x + 5y = 11$ I know how to calculate GCD $$5 = 1\cdot 3 + 2$$ $$3 = 1\cdot 2 + 1$$ $$2 = 2\cdot 1 + 0$$ But how do I use this theorem to derive the correct ...
2
votes
2answers
121 views

If $~a^3 + b^3 = c^3~$ has nonzero integer solutions and $~c-b~$ is a cubic number and $~c-b \neq 1$

If $~a^3 + b^3 = c^3~$ has nonzero integer solutions, because: $c^3 - b ^ 3 = (c - b)((c - b) ^ 2 + 3cb) = a ^ 3,\quad (1)$ if $~c-b~$ is a cubic number and $~c-b \neq 1~$, divide both side of ...
2
votes
3answers
82 views

How to solve this modular equation? $x^{19} \equiv 36 \mod 97$.

How to solve the following? $x^{19} \equiv 36 \mod 97$. I am having trouble figuring this out. Which technique do I need to use? Chinese Remainder or Fermat's Little Theorem?
3
votes
0answers
38 views

Are there infinitely many prime numbers in $a_n=\frac{7\times 10^n-1}{3}$?

In the array $a_n=\frac{7\times 10^n-1}{3}$, are there infinitely many primes? (when $n={7+16k},a_n$ is divisible by $17$, so there are infinitely numbers not prime)
2
votes
1answer
19 views

What is wrong with my 'counterexample' to the Blichfeldt Lemma?

We used a simplified version of the Blichfeldt lemma in our class, as follows: Lemma: Let $T \subset \mathbb R^n$ bounded with $V(T)>1$ ($n$-dimensional Volume). Then there exist $X',X'' \in T$, ...
1
vote
4answers
118 views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
1
vote
1answer
30 views

Division algorithm for the natural numbers.

I am trying to prove the following statement from Tao's analysis book. Definition of multiplication $ab++=ab+b$. Definition of addition $(a++)+b=(a+b)++$. Let $n$ be a natural number, and let $q$ ...
2
votes
1answer
50 views

The number of summands $\phi(n)$

If $n$ is a positive integer such that the sum of all positive integers $a$ satisfying $1\leq a\leq n$ and $gcd(a,n)=1$ is equal to $240n$ then the number of summands namely $\phi(n)$ is 120 124 ...
1
vote
2answers
47 views

Solving Multiple Equations with Many Variables

Here's a problem I have stumbled upon, which may have a straightforward solution with linear algebra. If so, I cannot see it. Choose $n > 0 \in \mathbb N$, and consider the sequence of equations: ...
3
votes
4answers
330 views

A consequence of Wilson's Theorem

By Wilson's Theorem we know that $$(p-1)! \equiv -1 \mod p.$$ A consequence of this is apparently $$(p-(k+1))!k! \equiv (-1)^{k+1} \mod p$$ where $0 \leq k \leq p-1$. I was told to think of it like ...
2
votes
1answer
68 views

Introductory Induction Proof

I am in currently in a discrete mathematics class, and I've done well on every problem I've encountered. Unfortunately, I find myself weak at some of the seemingly straight forward induction problems. ...
2
votes
0answers
36 views

Given a set of nonnegative numbers, put $\pm$ between them to minimize the magnitude of the result

Let's say I have a finite set of non-negative numbers. I have to put $+$ or $-$ between the numbers, in order to minimize the absolute sum.(i.e the sum has to be closest to 0) For example: the set: ...
2
votes
3answers
83 views

searching smallest number that has $40$ distinct positive divisors

What is the smallest natural number such that it has $ 40 $ distinct positive (integer) divisors (inclusive of $ 1 $ and itself? At first I was stunned of seeing the problem.It's not possible to find ...
0
votes
2answers
65 views

if $m$ and $n$ relatively prime integers different from $\pm 1$, there are unique integers $u$ , $v$ $\in Z$ such that $um+vn=1$ and $0 \le u \lt |n|$

Let $m$ and $n$ be relatively prime integers different from $\pm 1$. Show that there are unique integers $u$ , $v$ $\in Z$ such that $um+vn=1$ and $0 \le u \lt |n|$. In this case show that $|v| \lt ...
0
votes
1answer
30 views

Why does $\lfloor\frac{n}{x}\rfloor$ have at most $2\sqrt{n}$ values when $x=1,2,\dots n$?

The question is very short and clear: Why does $\lfloor\frac{n}{x}\rfloor$ (floor of $\frac nx$) have at most $2\sqrt{n}$ values when $x = 1, 2,\dots, n $? I saw this statement at tutorial of 449A ...
19
votes
5answers
3k views

What's wrong with this proof of the infinity of primes?

While reviewing an online textbook in abstract algebra for my website—which I'm hoping will go live by the end of the month—one of the exercises in the book inspired me to produce a simple, set ...
3
votes
2answers
56 views

Induction on GCD problem [duplicate]

This is a two part question Given $\gcd(a,b) = 1$ consider $$\gcd \left( \frac{a^n - b^n }{a-b}, a- b\right) $$ It appears that the value of this is always equal to $n$ or $1$. How to prove it? ...
3
votes
4answers
123 views

Tricky descent proof

EDIT: Please see EDIT(2) below, thanks very much. I want to prove by infinite descent that the only positive integer factors of integers of the form $a^2+3b^2$ have the same form. For example, ...
5
votes
1answer
381 views

how to show that the sequence of primes modulo 4 is not eventually periodic?

the question as posed is easily seen to be equivalent to asking how to show that a certain number is irrational. the number referred to as $\Phi$ is defined briefly beneath the question. it is a ...
1
vote
0answers
22 views

In $Z[x]$, which pairs of $a,b$ commute as modulo operators, such that ($c$ mod $a$) mod $b =$ ($c$ mod $b$) mod $a$ for every $c$?

In $Z[x]$, which pairs of $a,b$ commute as modulo operators, such that ($c$ mod $a$) mod $b =$ ($c$ mod $b$) mod $a$ for every $c$? What I got so far is: Clearly the equasion holds for every pair ...
27
votes
1answer
460 views

For integers $a\ge b\ge 2$, is $f(a,b) = a^b + b^a$ injective?

Given two integers $a \ge b \ge 2$, can we encode them as a unique integer $a^b + b^a$? This question was asked a few weeks ago, but did not rule out the trivial cases. For example, if we ...
0
votes
3answers
91 views

Triangular Numbers that are odd, less than 2000

The diagram below shows the $1$st, $2$nd, $3$rd and $4$th triangular numbers. (1 spot) : $1$ (3 spots) : $3$ (6 spots) : $6$ (10 spots) : $10$ The formula $n(n + 1)/2$ can be ...