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

learn more… | top users | synonyms

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
67 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
67 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 ...
3
votes
4answers
93 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
173 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
32 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
28 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
91 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
64 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
34 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
53 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
102 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
28 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
47 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
327 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
35 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
122 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
380 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
452 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
87 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 ...
0
votes
2answers
31 views

Alternative to using greater than operator for comparing numbers on a number line

The sign greater than "$>$" represents the quantity of one number more than another number. However the same sign is used to know the direction of a number on the numberline ( with respect to an ...
1
vote
0answers
63 views

An integer a is over 37, remainder is two unit smaller than the square of the quotient.

An integer $a$ is over $37$, remainder is two unit smaller than the square of the quotient. We want to know the maximum value of $a$ is divisible by which one of the following numbers? a.$9$ b.$12$ ...
4
votes
1answer
105 views

Elementary proof there are infinitely many primes of the form $4n+1$

My attempt: $4n+1$ is odd. Thus its decomposition must not contain $2$. Every odd number is either of the form $4k-1$ or $4m+1$. $(4m+1)(4k-1)$ is never of the form $4n+1$. So $4n+1$ has factors ...
1
vote
0answers
36 views

Find f(x,y) = 1 if(x=y) else 0 (f must only do addition/substraction multiplication or division)

This maybe more of a computer science problem but maybe the solution lies in number theory. Given integers x,y, find F(x,y) = 1 if x=y else F(x,y) = 0 The obvious solution Negate( x-y ) cannot be ...
-1
votes
2answers
105 views

Why is $y^{x-1}-1$ divisible by $x$?

I wanted to know if there is a way to prove that $y^{x-1}-1$ is divisible by $x$. Where $x$ is a prime number and is not equal to $y$, and $y$ is any positive whole number besides $1$. For example, ...
0
votes
2answers
54 views

For what integer values of $m$ and $n$ is $\frac{4m-n}{n}$ a rational square?

Question for what integer values of $m$ and $n$ with $(m,n)=1$ is $\frac{4m-n}{n}$ a rational square? Note the motivation for this question is a curiosity i noticed, that the smallest angle of the ...
1
vote
4answers
45 views

Subsets of divisors

How many subsets of the set of divisors of $72$ (including the empty set) contain only composite numbers? For example, $\{8,9\}$ and $\{4,8,12\}$ are two such sets. I know $72$ is $2^3\cdot 3^2$, so ...
4
votes
0answers
51 views

Does every integer $n > 2$ have a “reciprocating” pseudoprime $a$?

Such that $\gcd(a, n) = 1$, satisfying both $a^{n - 1} \equiv 1 \mod n$ and $n^{a - 1} \equiv 1 \mod a$? (And of course allowing for the idea of even pseudoprimes). From Fermat's little theorem it ...
2
votes
1answer
47 views

Given $n$, find smallest number $m$ such that $m!$ ends with $n$ zeros

I got this question as a programming exercise. I first thought it was rather trivial, and that $m = 5n$ because the number of trailing zeroes are given by the number of factors of 5 in $m!$ (and ...
0
votes
2answers
23 views

Remainder in Division using divisibility tests

I'm a bit lost / behind in my number theory class, but hey what can I do but try to catch up. I'm asked to find the remainder in division by $m= 3,7,9,11,13$ using divisbility tests for $1234567 ...
0
votes
1answer
43 views

Number Theory proof, help/tips would be appreciated

Let m and n be positive integers with gcd(m, n) = 1. Let A = {1, 2, ..., m} , B = {1, 2, ..., n} , X = {1, 2, ..., mn} , and let Y be the set of all ordered pairs (a, b) with a ∈ A and b ∈ B. (a) ...
9
votes
2answers
1k views

Why doesn't Fermat's Little theorem work for 4 and 9?

4 and 9 are relatively prime, but $4^8$ = 65536, which is not $1 \mod 9$. I can't figure out why because I've been told that $a^{p-1}$ is equivalent to $1 \mod p$ if $p$ and $a$ are relatively ...
2
votes
2answers
170 views

Chinese Remainder Theorem, redundant information

I want to solve the following system of congruences: $ x \equiv 1 \mod 2 $ $ x \equiv 2 \mod 3 $ $ x \equiv 3 \mod 4 $ $ x \equiv 4 \mod 5 $ $ x \equiv 5 \mod 6 $ $ x \equiv 0 \mod 7 $ I know, ...