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

learn more… | top users | synonyms (1)

0
votes
0answers
8 views

Why 82000? Numbers that can be written from base 2 to base 5 using only the digits 0 and 1

This is really badly curious. Many links on http://oeis.org/A146025 about this but -- why? I mean, this is not some abstract mathematical notation but rather something inherent in, I dunno, the ...
2
votes
2answers
48 views

if $p\mid a$ and $p\mid b$ then $p\mid \gcd(a,b)$

I would like to prove the following property : $$\forall (p,a,b)\in\mathbb{Z}^{3} \quad p\mid a \mbox{ and } p\mid b \implies p\mid \gcd(a,b)$$ Knowing that : Definition Given two ...
3
votes
2answers
42 views

Given $x^3$ mod $55$, find its inverse

So i am wondering how i can figure out what the functional inverse of $x^3$ mod $55$ is. I can only assume it is $x^{1/3}$ mod $55$ but i am not sure if that is the form i should keep it in
2
votes
1answer
28 views

What is the optimal strategy in a game where players subtract 7 or add or divide by 2?

I made up a nim type game where players start with a relatively high number and then for each turn if the number is odd, the player either subtracts 7 from the number or alternately if the number is ...
3
votes
1answer
25 views

Show that $2k\choose k$ divides the lcm of $1, \dots, 2k+1$

I want to show that $(2k+1){2k\choose k}$ is a factor of $\text{lcm}(1, \dots, 2k+1)$. Clearly the divisor is equal to $2^k\frac{1\cdot3\cdot\dots\cdot (2k+1)}{k!}$, but I don't know how to show that ...
5
votes
0answers
28 views

Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all ...
0
votes
0answers
27 views

If $ab^2+1 = c^2+d^2$ with $a$ squarefree, what [else] can be said about $a$?

What is known about squarefree integers $a$ where there exist integers $b$, $c$, and $d$ such that $$ab^2+1=c^2+d^2$$ ?
2
votes
0answers
24 views

Let $N=3^{1000}\times 2^{200009} +1$. Show that $5^{\frac{N-1}{2}}\equiv -1 \pmod{N}$.

This is showing that 5 is a quadratic non-residue mod N but I don't get why this says it is prime. The question also asks that you say that if p was prime divisor of N what the power of 2 dividing ...
0
votes
0answers
24 views

Number of solutions to a modular equation of a specific form

I struggle with this Exercise, or at least the part where one should prove how many solutions there are: Let $p$ be an odd prime, and let $e\in\mathbb{Z}$ with $e\gt 1$. Let $a$ be an integer of ...
0
votes
0answers
24 views
+50

Reference for zero sum problems?

I am looking for books/ references which deal with the analysis of zero sum problems and weighted zero sum problems. I have found some articles on the internet, but they seem insufficient. Any ...
1
vote
3answers
54 views

Integers divide several solutions to Greatest Common Divisor equation

I'm not sure about the topic's correctness but my problem is following: Suppose $u_1,v_1$ and $u_2,v_2$ are two different solutions for $au_i + bv_i = 1$, then $a \mid v_2-v_1$ and $b\mid u_1-u_2$. ...
8
votes
6answers
471 views

Fermat's Little Theorem: exponents powers of p

I was working with congruence classes and encountered Fermat's little theorem: $$a^{p } \equiv a \mod p$$ But I noticed that a$^{p^{k}} \equiv a \mod p$. I used induction on $k$ but I'm still not ...
0
votes
0answers
43 views

solution of the Pythagorean triple (a,b,21025)

I know that most intelligent people on this site will find this elementary question very simple (I hope you'll forgive me, I'm not yet familiar enough with mathematics): What is the solution of ...
2
votes
1answer
32 views

If $p$ is an odd prime show that $2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$

If $p$ is an odd prime show that $$2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$$ This is an exercise from Elementary Number Theory, 2nd Edition by Underwood Dudley. I know that the expression ...
49
votes
5answers
6k views

Are there an infinite number of prime numbers where removing any number of digits leaves a prime?

Suppose for the purpose of this question that number $1$ is a prime number. Consider the prime number $311$. If we remove one $1$ from the number we arrive at the number $31$ which is also prime. If ...
5
votes
1answer
564 views

Miller-Rabin primality test, begginer reading pseudo code

I was reading Miller-Rabin primality test Wiki and I can't understand something, it says that: Now, let $n$ be prime with $n > 2$. It follows that $n − 1$ is even and we can write it as $2s \cdot ...
0
votes
0answers
23 views

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite?

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite? Is there a general way to determine the number of ...
0
votes
0answers
18 views

Number of solutions to $f(x)\equiv 0 \mod(11\cdot 19^{2})$

I have been asked to explain why the number of solutions of the polynomial congruence $f(x)\equiv 0 \mod (11\cdot 19^{2})$ cannot be 121, where $f(x)=x^{10}+10x^{8}-17x+12$. Any ideas?
2
votes
2answers
59 views

Find triples $(a,b,c)$ of positive integers such that…

Find the triples $(a,b,c)$ of positive integers that satisfy $$\left(1+\frac{1}{a}\right)\left(1+\frac{1}{b}\right)\left(1+\frac{1}{c}\right)=3. $$ I found this on a local question paper, and I am ...
1
vote
1answer
18 views

Is a divides infinitely many repunits?

Let (a,10)=1 Let n=9k{phi(a)} using eulerphi function k is positive integer. When (a,9)= 1 , 3 it is okay Because 81 and a divides 10^n-1 by Binomial theorem and CRT So a divides (10^n-1)/9 ...
0
votes
0answers
11 views

Proof $\forall n \in \Bbb N$ that $2^n \cdot \prod_{i = 1}^{n} (2i-1)$ is divisible by $n!$

I'm trying to prove it by induction. $P(1)$ holds true. My inductive hypothesis is $n!\ |\ 2^n \frac {2n!} {2^n n!}$ which simplifies to $n!\ |\ \frac {2n!} {n!}$. Next $P(n+1)$: $$(n+1)!\ |\ 2^{n+1} ...
2
votes
1answer
38 views

Find all integer values of $x$ such that $x^2 + 13x + 3$ is a perfect integer square.

Question: Find all integer values of $x$ such that $x^2 + 13x + 3$ is a perfect integer square. What I have attempted; For $x^2 + 13x + 3$ to be a perfect integer square let it equal ...
2
votes
1answer
29 views

If $p>5$ is prime, $2p+1$ is a prime, $\frac{4p+1}{3}$ is prime, $8p+1$ is prime, Then $p \equiv 29 (mod \; 30)$

Assume that $p>5$ is prime, $2p+1$ is a prime, $\frac{4p+1}{3}$ is prime, $8p+1$ is prime. Then I want to prove that $p \equiv 29 (mod \; 30).$ First of all I have to show that $4p+1$ is a ...
2
votes
1answer
13 views

Boundedness of set with function on prime divisors

Let $P(n)$ denote the product of the prime divisors of $n$, e.g., $P(100)=2\times 5=10$. Define $$A=\{\frac{a}{P(ab(a-b))} \mid a,b\in\mathbb{Z}^+, a>b\}.$$ Is $A$ bounded or not? To make the ...
1
vote
1answer
37 views

Smallest positive integer r such that $8^{17} \equiv r \pmod {97}$

I want find out the Smallest positive integer r such that $8^{17} \equiv r \pmod{97}$. Fermat's theorem only tells us $8^{96} \equiv 1 \pmod{97}.$ How can I proceed. Any hint will be appreciated. ...
1
vote
3answers
56 views

Order of $5$ in $\Bbb{Z}_{2^k}$

Is it true that the order of $5$ in $\Bbb Z_{2^k}$ is $2^{k-2}$? I was unable solve the congruence $5^n\equiv 1\pmod {2^{k}}$ nor see why $5^{2^{k-2}}\equiv 1\pmod {2^{k}}$. I'm not sure if this is ...
1
vote
0answers
11 views

Integer division and congruence exercise

I'm just starting with integer division and congruence in an algebra course and I have this problem: Let $a$ be an odd integer. Prove that $\forall n \in \Bbb N$: $$2^{n+2}\ |\ a^{2^n} - 1$$ I've ...
-2
votes
1answer
41 views

Show that if $x = y + z$ , and $d$ is a divisor of any two of the integers $x$, $y$, and $z$, it is also a divisor of the third. [on hold]

Show that if $x = y + z$ , and $d$ is a divisor of any two of the integers $x$, $y$, and $z$, it is also a divisor of the third. How should I approach this problem and using what method to solve ...
1
vote
2answers
75 views

A prime number problem.

If $n$ is a positive integer and $(p_1,p_2,p_3,p_4,\ldots, p_n)$ are distinct positive primes, show that the integer $(p_1\cdot p_2\cdot p_3\cdot p_4\cdots p_n)+1$ is divisible by none of these ...
67
votes
12answers
7k views

Why 1 is not considered to be a prime number?

Why $1$ is not considered to be a prime number? Or why definition of prime numbers is given for integers greater than $1$?
3
votes
1answer
543 views

How to prove a generalized Gauss sum formula

I read the wikipedia article on quadratic Gauss sum. link First let me write a definition of a generalized Gauss sum. Let $G(a, c)= \sum_{n=0}^{c-1}\exp (\frac{an^2}{c})$, where $a$ and $c$ are ...
1
vote
1answer
17 views

Reference for table of cubes modulo $m$?

Is there an online table with all the cubes in $(\mathbb{Z}/m\mathbb{Z})$ (with $m$ up to (say) $100$, at least)? I didn't find anything googling it. Thanks.
0
votes
0answers
11 views

Which of a,b,c,d is/are odd given the set of conditions?

I am trying to answer this question. Which of a,b,c,d is/are odd given the set of conditions? Condition 1.) ad + bc is odd Condition 2.) ac + bd is odd The question is actually asking if we can ...
0
votes
1answer
15 views

Help with congruence and divisibility exercise

I'm starting to solve some problems of congruence and integer division, so the exercise is quite simple but I'm not sure I'm on the right track. I need to prove that the following is true for all $n ...
-1
votes
0answers
24 views

The prime divisors of $N= 3^{1000}.2^{2000009}+1$ are congruent to 1 modulo $2^{2000009}$

Let $N= 3^{1000}\cdot 2^{2000009}+1$. Assume that $5^{\frac{N-1}{2}} \equiv -1 \pmod N$. Let $p$ be a factor of $N$. Then my questions are the following: Which power of $2$ divides ...
2
votes
2answers
56 views

$7^{6} | (a+b+ab)^2$ Find the value of $a,b$ [on hold]

$7^{6} | (a+b+ab)^2$ Find the value of a,b. I have used trial and error for a singular solution. But a generalized solution will be helpful. Provide me the concept to deal with this problem and ...
0
votes
0answers
14 views

Understanding Primitve Root and Congruences relation.

Please help me understand following proof in very elementary way you can.
1
vote
1answer
53 views

a question about rational power irrational is irrational?

Please help me about the following question. Prove $2^e$ is an irrational number where $e$ is Neipper number. Thanks
2
votes
1answer
35 views

Find all $n$ such that $n|1^n + 2^n + 3^n + \cdots + (n-1)^n$ where $n \in \mathbb{Z}^+$.

Find all $n$ such that $$n|1^n + 2^n + 3^n + \cdots + (n-1)^n$$ where $n \in \mathbb{Z}^+$. I don't know how to start. $n = 3, 5$ are simple solutions. Induction seems strange since the divisor ...
0
votes
1answer
20 views

$n-1 = pq-1 \equiv q-1\pmod{p-1}$ where $n\in\mathbb{N}$ such that $n=pq$ for two distinct large primes $p$ and $q$.

Let $n\in\mathbb{N}$ such that $n=pq$ for two distinct large primes $p$ and $q$. My lecturer simply states that $$n-1 = pq-1 \equiv q-1\pmod{p-1}$$ without any justification and I can't see how this ...
0
votes
0answers
31 views

$\Bbb N \times \Bbb N$ is countable induction

I was trying to to prove $\Bbb N \times \Bbb N$ is countable, If I let $f:\Bbb N \times \Bbb N \to \Bbb N$ be given by $f((m,n))= m+\sum_{i=0}^{m+n-2}i$ then $f(1,1) = 1\\ f(1,2) = 2\\ ...
-3
votes
1answer
39 views

Elements of Number Theory [on hold]

i) Show that if $\gcd(a,n) = 1$ and $\gcd(b, n) = 1$ then $\gcd(ab,n) = 1$. ii) Show that if $\gcd(c, n) = 1$ then for all we have $a \equiv b \pmod n$ if and only if $ca \equiv cb \pmod n$.
1
vote
1answer
50 views

Determining a multiple of a power of 2.

I am thinking about this question which I believe is a possible GRE question. "Which of the following numbers is exactly divisible by 32? A) $1.9 \times 10^5 $ B) $1.9 \times 10^6$ C) $1.9 \times ...
0
votes
1answer
21 views

Sum of primes less than or equal to K is greater than K

I am trying to show that the sum of primes less than or equal to some $k \in \mathbb{N}$ must be greater than $k$ itself. My hint was to use Bertrands Postulate but I am not getting anywhere.
0
votes
0answers
15 views

Using the fact that 6 is a primitive root modulo 109, compute the remainder when 424^2076 divided by 109

Using the fact that 6 is a primitive root modulo 109, compute the remainder when $424^{2076}$ is divided by 109. I try with ord_109 (6)=phi(109) =108 424 = 97mod 109 stuck here
0
votes
1answer
39 views

Understanding a proof of a corollary in chapter 2 about invertibility of a p-adic integer (Jean-Pierre Serre)

In a proof of a corollary in chapter 2, there is a step I don't understand. Corollary 2: Suppose $p \neq 2$. Let $f(X) = \sum_j a_{ij}X_iX_j$ with $a_{ij} = a_{ji}$ be a quadratic form with ...
0
votes
3answers
65 views

Determine: $13^{-1} \pmod {67}$

Determine: $13^{-1} \pmod {67}$ I'm not sure how to deal with the negative one here as it inverts the integer? Any help would be appreciated!
7
votes
1answer
412 views

What is the period of this sequence?

Consider the recurrence relation: $$x_{i+1}=p-1-((p \cdot i-1) \mod{x_i})$$ If $p$ is prime and $x_0=1$, what is the least period of the resulting (eventually periodic) sequence? My guess is the ...
11
votes
3answers
121 views

Why is the Fundamental Theorem of Arithmetic so important?

I've recently read about the Fundamental Theorem of Arithmetic and I think that I have just about understood the proof. What I found quite interesting at first was the "Fundamental" part in the name. ...
1
vote
3answers
46 views

If $p$ and $q$ are positive prime numbers such that $p$ is divisible by $q$, show that $p = q$.

To solve this problem, this is my approach. Assume $p\mid q$, there exists an $n∈N$ and assume $q\mid p$, there exists an $m∈N$. This would mean that $p=qn$ and $q=pm$. Then using substitution, ...